특정 노드 2개를 선택해서 쭉 늘렸을 때, 가장 길이가 긴 두 노드를 찾아야 한다. 이 길이를 문제에서는 트리의 지름이라고 칭합니다.
1번 노드부터 탐색해서 가장 가중치가 큰 노드 하나를 선택합니다.
가장 가중치가 큰 노드는 반드시 트리의 지름의 한 점이 된다고 생각했습니다.
가장 가중치가 큰 노드를 하나 선택했으면, 해당 노드부터 BFS로 다시 탐색을 시작해서 가장 길이가 긴 값(트리의 지름)을 반환합니다.
2. 접근 과정에서 실수했던 부분
문제에서 "간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다."라는 부분이 있었습니다.
이 부분을 잘못 이해해서 다음과 같이 문제 접근을 시작했습니다.
(1) 입력을 받으면서 가장 가중치가 큰 노드를 선택
Node[] nodes = new Node[n + 1]; // 가장 가중치가 큰 노드를 찾기 위한 배열
nodes[0] = new Node(0, 0); // NullPointerException 방지를 위해
nodes[1] = new Node(1, 0); // 1번은 루트이기 때문에 가중치가 0
for (int i = 1; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int first = Integer.parseInt(st.nextToken());
int second = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
map[first].add(new Node(second, weight)); // 트리의 양방향 설정
map[second].add(new Node(first, weight)); // 트리의 양방향 설정
int beforeWeight = nodes[first] == null ? 0 : nodes[first].weight;
nodes[second] = new Node(second, beforeWeight + weight);
}
Arrays.sort(nodes, (n1, n2) -> n2.weight - n1.weight);
// 도달 거리가 가장 큰 놈을 하나 선택
int start = nodes[0].end;
O(N)에 모든 것을 다 챙겨가려는 오만한 생각에 코드를 이렇게 짰습니다.
이렇게 해서 문제 제출을 해보니 67%쯤에서 계속 틀렸다고 나왔습니다.
(2) 도움이 됐던 반례
이진 트리라는 조건이 없어서 생겼던 웬만한 반례들은 모두 통과가 됐습니다.
그래서 처음에는 어느 부분에서 실수를 한지 판단할 수가 없어서 계속 생각해 보다가 알고리즘에 도움을 줬던 반례가 있었습니다.
"간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼저 입력된다."라는 조건은 확실하게 만족하는 입력 값들이었습니다.
제 알고리즘대로라면 {2 5 1}이 입력되었을 때, 5라는 노드의 가중치는 2라는 노드의 가중치에 1을 더한 값이 세팅되어야 합니다. 하지만 위 입력에서는 아직 노드 2에 대한 제대로 된 가중치가 저장되기 전이기 때문에 옳지 않은 정답을 출력한 것을 알 수 있습니다.
3. 문제 해결
기존의 나머지 알고리즘은 그대로 두고, 문제가 있던 입력받는 부분에 대해서만 수정을 했습니다.
입력은 그대로 인접 리스트를 사용하여 양방향 정보를 저장하고, BFS 탐색을 2번 했습니다.
첫 번째 탐색에서는 가중치의 최대값을 갱신하면서 그 최대 가중치를 갖는 노드(start)를 찾아냈습니다.
두 번째 탐색에서는 최대 가중치를 갖는 노드(start)부터 다시 탐색을 시작해서 가장 가중치가 긴 값(트리의 지름)을 갱신해서 반환했습니다.
import java.io.*;
import java.util.*;
public class Main {
static int n, start;
static List<Node>[] map;
static boolean[] visited;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/main.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
map = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) {
map[i] = new ArrayList<>();
}
for (int i = 1; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int first = Integer.parseInt(st.nextToken());
int second = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
map[first].add(new Node(second, weight));
map[second].add(new Node(first, weight));
}
// 가장 큰 노드를 탐색
visited = new boolean[n + 1];
bfs(1);
// 해당 노드부터 탐색을 시작해서 최장 거리를 찾음
visited = new boolean[n + 1];
int result = bfs(start);
System.out.println(result);
}
public static int bfs(int startNodeNumber) {
int result = 0;
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(startNodeNumber, 0));
visited[startNodeNumber] = true;
while (!queue.isEmpty()) {
Node curr = queue.poll();
if (result < curr.weight) {
result = curr.weight;
start = curr.end;
}
for (Node node : map[curr.end]) {
if (visited[node.end]) continue;
queue.add(new Node(node.end, curr.weight + node.weight));
visited[node.end] = true;
}
}
return result;
}
static class Node {
int end;
int weight;
public Node(int end, int weight) {
this.end = end;
this.weight = weight;
}
}
}
