백준 1167 트리의 지름

문제

풀이

public class Q1167_트리의지름 {

    static ArrayList<Node>[] arr;
    static boolean[] visited;
    static int[] distance;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());

        arr = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) {
            arr[i] = new ArrayList<>();
        }
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            while (true) {
                int e = Integer.parseInt(st.nextToken());
                if (e == -1) {
                    break;
                }
                arr[s].add(new Node(e, Integer.parseInt(st.nextToken())));
            }
        }
        distance = new int[n + 1];
        visited = new boolean[n + 1];

        // 일단 임의의 노드와 거리가 가장 먼 노드를 구함
        // 현재 가장 먼 두 개의 노드가 무엇인지 모르므로 임의의 노드를 지정해
        // 그 노드와 가장 멀리있는 노드부터 찾음
        bfs(1);
        int max = 1;
        for (int i = 2; i <= n; i++) {
            if (distance[max] < distance[i]) {
                max = i;
            }
        }
        // 거리 배열과 방문 배열을 초기화
        distance = new int[n + 1];
        visited = new boolean[n + 1];

        // 앞에서 찾은 가장 멀리 있는 노드를 기준으로
        // 그 노드와 가장 멀리 떨어져있는 노드를 찾음
        bfs(max);
        Arrays.sort(distance);
        System.out.println(distance[n]);

    }

    public static void bfs(int idx) {
        Queue<Integer> q = new LinkedList<>();
        q.add(idx);
        visited[idx] = true;
        while (!q.isEmpty()) {
            int now = q.poll();
            for (Node i : arr[now]) {
                int next = i.next;
                int val = i.distance;
                if (!visited[next]) {
                    visited[next] = true;
                    q.add(next);
                    distance[next] = distance[now] + val;
                }
            }
        }
    }

    static class Node {
        int next;
        int distance;

        public Node(int next, int distance) {
            this.next = next;
            this.distance = distance;
        }
    }
}

리뷰

bfs를 사용해서 풀어야 한다는 것을 알겠는데,
서로 거리가 가장 먼 노드를 구하는 방법이 잘 떠오르질 않았다.

이 문제의 흐름?은 다음과 같다.

1. 먼저 입력된 노드중 임의의 노드를 시작지점으로 설정하고 bfs를 진행한다.
   • 이때 bfs에서는 시작지점에서 가장 멀리 떨어져 있는 노드를 구한다.
     따라서 시작지점부터 끝지점까지 거리를 누적해줘야한다.
   • 이 과정중에 서로 가장 멀리 떨어져 있는 노드중 하나의 노드를 구하게 된다.
2. 방문 배열과 거리 누적합 배열을 초기화해준다.
3. 1번을 통해 구한 노드를 기준으로 bfs를 진행하여 나머지 가장 멀리 떨어진 노드를 구한다.
   • 이때도 마찬가지로 bfs를 진행하며 현재 노드와 가장 멀리 떨어져 있는 노드의 거리를 누적한다.
4. 3번 과정을 통해 구해진 거리를 출력한다.

다른 bfs를 혼자서 풀어내서 자신감이 오를뻔 했는데 그러다 말았다ㅜ