백준 1167. 트리의 지름

문제. 백준 1167 : 트리의 지름

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

입력

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

출력

첫째 줄에 트리의 지름을 출력한다.

풀이

으음,,,,,, 답안 찾아봤다. 고민하다가 안풀려서
트리의 지름 어떻게 구하지? 가장 깊숙하게 위치한 노드를 찾아야하나? 아니지 깊더라도 노드 간의 거리가 짧은 노드들끼리 잔뜩 연결되어있으면 깊어도 거리가 짧을 수 있으니까,,,,

트리의 지름을 구하기 위해서는 임의의 점에서 시작해도 상관 없다. 임의의 점에서 dfs 또는 bfs를 사용해서 모든 노드들까지의 거리를 탐색한다. 임의의 점에서 시작하여 가장 거리가 먼 지점의 노드를 찾는다. 가장 먼 노드를 a라고 하자. 그럼 우리는 a노드에서 다시 bfs, dfs를 사용하여 가장 거리가 먼 지점의 노드를 찾는다. 이때 찾게 되는 노드를 b라 하자. 이 노드 b까지의 거리가 트리의 지름이 된다.

트리의 지름 구하는 방법
1. 임의의 노드 a에서 가장 먼 노드 b를 찾는다.
2. 노드 b에서 가장 먼 노드 c를 찾는다.
3. 노드 b와 노드 c를 연결하면 트리의 지름이 된다.

트리의 지름 구하는 방법만 알았고 나머지는 스스로 생각해서 풀었다. 뭐 지름 구하는 방법만 알면 다른 길찾기 문제나 다른 것도 없다. 다른 풀이들에서 dfs도 많은데 공부하던 책의 챕터가 bfs이기도 했어서 bfs로 해결하였다.

풀이 코드 java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class boj1167 {
    static int n;
    static ArrayList<int[]>[] arr;
    static boolean[] visited;
    static int[] distance;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer stk;
        arr = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            arr[i] = new ArrayList<int[]>();

        }
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            int idx = Integer.parseInt(stk.nextToken()); // 입력받은 노드의 인덱스
            while (true) {
                int node = Integer.parseInt(stk.nextToken());
                if (node == -1)
                    break;
                arr[idx].add(new int[]{node, Integer.parseInt(stk.nextToken())});
            }
        }

        visited = new boolean[n + 1];
        distance = new int[n + 1];

        int max_idx = 1;
        bfs(1);
        for (int i = 1; i <= n; i++) {
            if (distance[i] > distance[max_idx]) {
                max_idx = i;
            }
        }

        visited = new boolean[n + 1];
        distance = new int[n + 1];
        bfs(max_idx);
        Arrays.sort(distance);
        System.out.println(distance[n]);
    }

    static void bfs(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();

            for (int[] ints : arr[node]) {
                int x = ints[0]; // x번 노드
                int d = ints[1]; // x번 노드까지의 이동 거리

                if (visited[x])
                    continue;

                queue.add(x);
                visited[x] = true;
                distance[x] = distance[node] + d;
            }
        }
   }
}

풀이 코드 python

from collections import deque
n = int(input())
graph = [[] for i in range(n+1)]
for i in range(1, n+1):
    nodes = list(map(int,input().split()))
    idx = nodes[0]
    nodes = nodes[1:-1]
    for j in range(0, len(nodes), 2):
        graph[idx].append((nodes[j], nodes[j+1],))

visited = [False] * (n+1)
distance = [0] * (n+1)
def bfs (start):
    queue = deque([start])
    visited[start] = True
    while queue:
        n = queue.popleft()
        for i in graph[n]:
            if not visited[i[0]]:
                queue.append(i[0])
                distance[i[0]] = distance[n] + i[1]
                visited[i[0]] = True

bfs(1)
max_idx = 0
for i in range(1, n+1):
    if distance[max_idx] < distance[i]:
        max_idx = i

visited = [False] * (n+1)
distance = [0] * (n+1)
bfs(max_idx)
print(max(distance))