트리의 지름
역할
- 그래프가 주어졌을 때, 트리의 최대 지름값과 양 끝 노드를 알 수 있다.
알고리즘
- 전체 노드의 거리를 저장하는
int[] visit = new int[n+1];을 생성한다. - 임의의 노드에서 최대 거리에 위치한 노드를 찾는다.
node firstNode = getTreeDiameter(1); - 임의의 노드에서 찾은 최대 노드(firstNode)에서 최대 거리에 위치한 노드를 찾는다.
node secondNode = getTreeDiameter(firstNode.num); - 이때 찾게 된
secondNode는 무조건 트리의 지름의 양 끝 중 하나이다. - visit[i]를 탐색하며 지름의 길이와 일치하는 노드가 2개 이상이라면 firstNode와 secondNode는 지름의 양끝이다.
if(visit[i] == secondNode.weight) cnt++; - 그렇지 않다면 secondNode에서 최대 거리에 위치한 노드를 찾는다.
node firstNode = getTreeDiameter(secondNode.num); - 트리의 양 끝 노드는 firstNode와 secondNode가 된다.
관련 문제 : 프로그래머스 - 트리 트리오 중간값
- 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public static void solution(int n, int[][] edges){
vector = new Vector[n+1];
for(int i=1; i<=n; i++){
vector[i] = new Vector<>();
}
for(int i=0; i<edges.length; i++){
int v1 = edges[i][0];
int v2 = edges[i][1];
vector[v1].add(new node(v2, 1));
vector[v2].add(new node(v1, 1));
}
visit = new int[n+1];
// 임의의 노드에서 최대 거리에 위치한 노드를 구한다.
int first_num = 1;
node firstNode = getTreeDiameter(first_num);
// 위에서 구한 노드에서 최대 거리에 위치한 노드를 구한다.
visit = new int[n+1];
node secondNode = getTreeDiameter(firstNode.num);
// secondNode는 무조건 지름의 끝에 위치한 노드 중 하나가 된다.
int len = secondNode.weight;
int cnt = 0;
for(int i=1; i<=n; i++){
// visit[i] 중 트리의 지름에 해당하는 값을 갖고 있는 것이 2개 이상이라면 중간값은 무조건 트리의 지름이 된다.
// ex) (1,3,3)->3 (2,3,3)->3
if(visit[i] == len){
cnt++;
}
if(cnt>=2) {
System.out.println(len);
return;
}
}
// 2개 이상이 아니라면 firstNode가 지름의 끝이 아니므로 secondNode에서 최대 거리에 위치한 노드를 구한다.
visit = new int[n+1];
firstNode = secondNode;
secondNode = getTreeDiameter(secondNode.num);
len = secondNode.weight;
cnt = 0;
for(int i=1; i<=n; i++){
// visit[i] 중 트리의 지름에 해당하는 값을 갖고 있는 것이 2개 이상이라면 중간값은 무조건 트리의 지름이 된다.
if(visit[i] == len){
cnt++;
}
if(cnt>=2) {
System.out.println(len);
return;
}
}
// 지름의 끝에 해당하는 노드가 두개이므로 중간값은 지름-1이 된다.
System.out.println(secondNode.weight-1);
return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Queue를 활용해 BFS를 돌면서 s노드 기준 연결된 모든 노드의 거리를 알 수 있다.
static node getTreeDiameter(int s){
int max = 0;
int n = 0;
Queue<node> queue =new LinkedList<>();
queue.add(new node(s, 0));
visit[s] = 0;
while(!queue.isEmpty()){
node temp = queue.poll();
for(node next : vector[temp.num]){
if(visit[next.num] == 0 && next.num!=s) {
visit[next.num] = visit[temp.num] + 1;
if(max<visit[next.num]){
max = visit[next.num];
n = next.num;
}
queue.add(new node(next.num, visit[next.num]));
}
}
}
return new node(n, max);
}