[ 백준 ] 1167번 트리의 지름 (Java 자바)

🔗 문제 링크: 백준 1167번 - 트리의 지름

문제 설명

주어진 가중치가 있는 트리에서 두 노드 사이의 최대 거리를 구하는 문제이다.
즉, 트리의 모든 두 노드 사이의 거리 중 가장 긴 값을 구하면 그것이 트리의 지름이다.

입력 조건

• 첫 줄: 노드의 개수 N
• 다음 N줄: 각 줄은 시작 노드 번호와, 해당 노드와 연결된 노드 번호 및 가중치 쌍이 주어지고, -1로 종료된다.
  예를 들어, 한 줄의 입력은 "1 3 2 2 3 -1"과 같이 주어질 수 있다.

---

풀이 과정

📌 문제 요약

• 가중치가 있는 트리에서 두 노드 사이의 최대 거리를 구하는 문제이다.
• 트리의 지름은 임의의 두 노드 사이의 거리 중 가장 긴 값이다.
• DFS를 두 번 수행하는 방식으로 문제를 해결한다.

📌 DFS를 두 번 수행하면 트리의 지름이 나오는 이유?

 

• 트리의 특성:
  트리는 사이클이 없고, 모든 두 노드 사이에 유일한 경로가 존재한다.
  따라서 임의의 노드에서 가장 멀리 있는 노드는 항상 트리의 한쪽 끝에 위치한다.
• 끝점(Leaf)의 성질:
  첫 번째 DFS에서 얻은 노드 B는 끝점일 가능성이 매우 높으며, 트리의 지름은 항상 두 끝점 사이의 최단 경로이다.
  두 번째 DFS를 B에서 시작하면, B와 가장 먼 노드 C까지의 경로가 결국 트리의 지름이 된다.
• 증명 아이디어:
  임의의 노드 A에서 가장 멀리 떨어진 노드를 B라고 하자.
  만약 B가 트리의 지름의 한 끝점이 아니라면, 트리의 지름은 A보다 B보다 더 먼 곳에 존재하게 되는데, 이는 A에서 DFS로 B를 선택한 조건과 모순된다.
  따라서, B는 트리의 지름의 한 끝점이 되며, B에서 다시 가장 멀리 떨어진 노드 C까지의 거리가 트리의 지름임을 알 수 있다.

 

📌 해결 전략

1. 첫 번째 DFS:
   임의의 노드(여기서는 1번 노드)에서 시작하여 가장 멀리 떨어진 노드를 찾는다.
2. 두 번째 DFS:
   첫 번째 DFS에서 찾은 가장 먼 노드에서 시작하여 다시 DFS를 수행해 최대 거리를 구한다.
3. 결과:
   두 번째 DFS에서 구한 최대 거리가 트리의 지름이 된다.

📌 풀이 과정 (DFS)

• DFS 함수는 현재 노드에서 상하(연결된 노드)로 이동하면서 누적 거리를 계산한다.
• 방문 배열(visited)을 사용해 중복 방문을 방지한다.
• DFS 중에 누적 거리가 현재 최대값보다 크면 최대값과 해당 노드를 갱신한다.
• 첫 번째 DFS로 얻은 가장 먼 노드에서 다시 DFS를 수행하여 트리의 지름을 구한다.

📌 시간 복잡도 분석

• 각 DFS는 노드 수 N에 대해 O(N) 시간이 소요된다.
• 두 번의 DFS를 수행하므로 전체 시간 복잡도는 O(2N), 즉 O(N)이다.
• 트리의 특성상 모든 노드를 한 번씩 방문하므로 효율적인 풀이이다. 👍

---

🔥 최종 정리 및 코드

임의의 노드에서 DFS를 실행해 가장 멀리 있는 노드를 찾고, 그 노드에서 다시 DFS를 수행해 트리의 지름(최대 거리)를 구한다.
방문 배열을 통해 중복 방문을 방지하며, DFS 과정에서 누적 거리와 최대값을 갱신하는 방식으로 문제를 해결한다.

 

package Graph;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.io.IOException;

/*
    BOJ Gold 2, 트리의 지름
    문제 링크: https://www.acmicpc.net/problem/1167

    트리의 지름이란, 임의의 두 점 사이의 거리 중 가장 긴 것이다.
    가중치가 있는 무방향 그래프(트리)에서, 
    임의의 노드에서 DFS를 통해 가장 멀리 떨어진 노드와 그 거리를 기록하고,
    그 노드에서 다시 DFS를 수행하면 트리의 지름을 구할 수 있다.
*/

public class BOJ_G2_1167 {
    static int N;                          // 노드의 개수
    static List<int[]>[] tree;             // 인접 리스트 (각 노드와 연결된 [노드, 가중치] 쌍들을 저장)
    static boolean[] visited;              // 방문 여부 배열
    static int maxDist = 0;                // 현재까지 기록된 최대 거리
    static int longestNode = 0;            // 현재 DFS에서 가장 먼 노드

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());   // 노드의 개수 입력

        // 트리 생성: 1번 노드부터 N번 노드까지 사용하므로 N+1 크기로 초기화
        tree = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) {
            tree[i] = new ArrayList<>();       // 각 노드의 인접 리스트 생성
        }

        // 각 노드의 인접 정보 입력 (노드 번호, 가중치 쌍들이 -1이 나올 때까지)
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken()); // 현재 노드 번호
            while (true) {
                int v = Integer.parseInt(st.nextToken());
                if (v == -1) break;
                int w = Integer.parseInt(st.nextToken());
                tree[u].add(new int[]{v, w});  // 노드 u에 연결된 (노드 v, 가중치 w) 추가
            }
        }

        // 첫 번째 DFS: 임의의 노드 (여기서는 1번)에서 시작하여 가장 먼 노드 탐색
        visited = new boolean[N + 1];
        dfs(1, 0);

        // 두 번째 DFS: 첫 번째 DFS에서 찾은 가장 먼 노드에서 시작하여 트리의 지름 계산
        visited = new boolean[N + 1];
        maxDist = 0;
        dfs(longestNode, 0);

        // 트리의 지름 출력
        System.out.println(maxDist);
    }

    // DFS 함수: 현재 노드에서 시작하여 누적 거리를 계산하면서 가장 먼 노드를 찾음
    static void dfs(int node, int dist) {
        // 현재까지의 누적 거리가 최대값보다 크면 갱신
        if (dist > maxDist) {
            maxDist = dist;
            longestNode = node;
        }
        visited[node] = true;  // 현재 노드 방문 처리

        // 인접 리스트에 저장된 모든 연결 노드에 대해 DFS 수행
        for (int[] next : tree[node]) {
            if (!visited[next[0]]) {
                dfs(next[0], dist + next[1]);  // 연결 노드로 이동하면서 누적 거리에 가중치 추가
            }
        }
    }
}