BOJ_1167 : 트리의 지름

👉 문제링크

1167번: 트리의 지름

---

---

🔸 문제 분석 🔸

• 노드 사이 거리(가중치)가 있는 트리에서 가장 먼 거리를 구한다.
  • 어느 부분 가중치가 큰 값이든 트리의 지름 양 끝은 리프 노드일 것이다. (큰 가중치 부분을 반드시 지남)
  • 트리이기 때문에 두 노드 사이의 경로는 하나로 유일하다.
  • 한 노드에서 가장 먼 노드를 구하면, 그 노드가 트리의 지름 양 끝 리프 노드 중 하나이다.
• DFS 두 번으로 풀이할 수 있다.
  • DFS 1 : 아무 노드에서 가장 먼 노드를 구한다.
  • DFS 2 : 구한 노드에서 다시 가장 먼 노드를 구하면, 그 거리가 트리의 지름이다.

🔸 코드 🔸

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private static class Edge {
        int node, weight;

        public Edge(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }

    private static ArrayList<Edge>[] nodeList;
    private static boolean[] visited;

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

        int V = Integer.parseInt(br.readLine());

        nodeList = new ArrayList[V + 1];

        for (int i = 1; i <= V; i++) {
            nodeList[i] = new ArrayList<>();
        }

        for (int i = 0; i < V; i++) {
            st = new StringTokenizer(br.readLine());
            int node_number = Integer.parseInt(st.nextToken());

            while (true) {
                int node = Integer.parseInt(st.nextToken());
                if (node == -1) break;
                int weight = Integer.parseInt(st.nextToken());
                nodeList[node_number].add(new Edge(node, weight));
            }
        }

        visited = new boolean[V + 1];
        Edge start_point = dfs(1, 0);

        visited = new boolean[V + 1];
        Edge end_point = dfs(start_point.node, 0);

        bw.write(Integer.toString(end_point.weight));
        bw.flush();
    }

    private static Edge dfs(int now, int weight) {
        visited[now] = true;

        int max = 0;
        Edge temp = null;
        Edge result = new Edge(now, weight);

        for (Edge next : nodeList[now]) {
            if (!visited[next.node]) {
                temp = dfs(next.node, next.weight + weight);
                if (temp.weight > max) {
                    max = temp.weight;
                    result = temp;
                }
            }
        }
        return result;
    }
}

🔸 코드 해석 🔸

• 멤버 클래스/변수 선언
  • 노드 번호와 가중치를 저장할 간선 클래스 Edge를 만들어 사용했다.
  • 노드별 인접 리스트를 저장하기 위한 ArrayList 배열 nodeList를 사용했다.
  • DFS에서 방문체크를 위한 boolean 배열 visited를 사용했다.
• 노드 간 연결 정보를 nodeList에 입력받았다.
• dfs 메서드를 통해 DFS를 구현하고, 가장 먼 노드와 그 가중치를 Edge 객체로 반환했다.
  • 현재 노드를 방문체크한다.
  • 연결된 모든 노드를 DFS로 탐색 후 가장 먼 노드의 번호와 그 가중치를 result에 담는다.
  • 만약 리프노드라면(방문할 인접 노드가 없다면), 현재 노드와 가중치를 반환한다.

---

🔸 end 🔸

문제의 분석과 풀이를 적어가며 진행했다.

• 처음엔 한 노드에서 다른 모든 노드까지의 거리를 구해야 되나 싶어서 다익스트라, 프림 알고리즘을 생각했다. 하지만, 최단경로를 구하는 문제가 아니고 경로가 유일해서 갱신이 일어나지 않아 변형해서 사용하거나 올바르지 않다고 생각했다. (질문 중엔 다익스트라 사용으로 통과되었다는 말은 보았다)
• 다음 생각한 방법은 위와 같이 모든 노드 거리를 구하면서 메모이제이션을 이용하는 것인데, 노드 수가 10만개다보니 메모이제이션으로는 메모리가 초과할 것 같았다. (중앙 노드 하나고, 그 외에 별모양으로 연결되어 있는 방식의 극다적인 모양이 있다면..)
• 결과적으로 두 풀이는 포기했다.

• 질문과 포스팅을 확인해 풀이 방법을 확인해보니 생각보다 간단한 DFS 2번으로 풀이가 가능했다.
• 이런 풀이가 가능한 직관적인 방법은 질문 게시판에서 좋은 예시를 찾았다. (질문 게시판 힌트 글)
  • 노드를 구슬, 간선을 실로 비유해서 어느 한 구슬을 잡고 늘어뜨리면 가장 먼 구슬이 나타난다.
  • 그 구슬을 잡고 다시 한 번 늘어뜨리면 가장 먼 구슬 까지의 거리가 트리의 지름이 된다.
• 다른 정리로 포스팅 글을 보았다. (풀이 포스팅)
  • 문제에 주어진 예시로 설명해주셨는데, 각 노드 별 최장거리의 노드를 적어보니 트리의 지름의 노드들이었다.
  • 트리의 지름이 되는데 결정적인 역할을 하는 가중치를 지름 노드들은 반드시 지나고, 각 노드에서 최장거리 노드로 갈 때도 지나는 것이다. (완벽한 설명은 아니다)
  • 아무튼 임의의 노드에서 최장거리 노드를 구하고, 다시 한 번 구하면 된다.
• 그래프 탐색에 DFS를 선택하는 이유는 최장거리를 계속 비교하며 찾아야하니, 재귀 속 간단한 메모이제이션이 필요했기 때문이다. BFS는 당연 메모리 초과가 날 것이다.
• 트리에 대한 독특한 특징을 알 수 있었던 문제였다.