[LeetCode][Union-Find] 2421. Number of Good Paths

[English]

 

[Korean]

[문제 해석]

There is a tree (i.e. a connected, undirected graph with no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges.

트리는 사이클이 없는 무방향 그래프이다. n개의 노드(정점)와 n-1개의 간선으로 구성된 트리가 있다.

You are given a 0-indexed integer array vals of length n where vals[i] denotes the value of the ith node. You are also given a 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.

vals[i]는 i번째 노드의 값을 나타내는 길이 n의 0 부터 시작하는 정수 배열이 주어진다. 또한, 간선 edges[i]를 나타내는 2차원 정수 배열이 주어진다. edges[i] = [ai, bi]는 노드 ai 와 bi사이를 연결하는 간선이 있다는 것을 의미한다.

A good path is a simple path that satisfies the following conditions:

다음의 조건을 만족하는 경로는 good path이다.

1. The starting node and the ending node have the same value.
2. All nodes between the starting node and the ending node have values less than or equal to the starting node (i.e. the starting node's value should be the maximum value along the path).

 

1. 시작 노드와 마지막노드는 같은 값이다.
2. 시작 노드와 마지막 노드 사이에 있는 모든 노드는 시작 노드의 값보다 작거나 같은 값을 가진다. = 시작 노드가 경로에서 가장 큰 값을 가져야한다.

 

Return the number of distinct good paths.

가능한(고유한) good path의 개수를 반환하라.

Note that a path and its reverse are counted as the same path. For example, 0 -> 1 is considered to be the same as 1 -> 0. A single node is also considered as a valid path.

역방향도 같은 경로임에 주의해라. 예를들어, 0->1 과 1->0은 같은 경로다. 단일 노드는 유효한 경로로 구분된다.

 

[문제 분석]

 

[좋은 표현]

(시작 할 때) 직관적인 접근(방법)으로는.. =>An intuitive approach would be to start from a node and traverse to its neighbors, which have a lower value than the node.

같은 동작을 반복할 수 있다. 이러한 방법으로,, 모두 돌수있다~ => We can repeat the same process for every node in the tree. In such a way, we traverse the tree.

볼 필요가 없다 => There is no point in traversing from...

제약사항을 위반한다. => It violates the good path constraints.

직관적으로, 힌트를 얻을 수 있다. => Intuitively, this does give some hints about sorting the nodes according to their values, starting with the samllest value first and then going to higher values.