[1167] 트리의 지름

✔ 트리의 지름

[백준 1167]

문제 분석하기

임의의 노드에서 가장 긴 경로로 연결돼 있는 노드는 트리의 지름에 해당하는 두 노드 중 하나이므로

BFS를 수행하여 탐색할 때 각 노드의 거리를 배열에 저장하며 노드 하나를 찾은 후,

그 노드를 기준으로 각 노드의 거리 배열을 업데이트하여 가장 큰 값이 트리의 지름이 되는 것으로 문제에 접근

손으로 풀어보기

1. 그래프를 인접 리스트레 저장
   • 정점 번호(노드)와 정점까지의 거리(가중치)를 표현하기 위해 노드를 클래스로 선언
2. 임의의 노드에서 BFS를 수행하고 탐색할 때 각 노드의 거리를 배열에 저장
3. 앞서 얻은 배열에서 임의의 노드와 가장 먼 노드를 찾아 그 노드부터 BFS를 다시 수행하며 각 노드의 거리를 배열에 저장
   • 노드의 거리 배열을 업데이트
4.  배열에 저장한 값 중 가장 큰 값을 트리의 지름으로 출력

예) 임의의 노드 중 노드 2에서 탐색을 시작하는 경우

depth1	depth2	depth3	depth4	거리 배열
2 (임의의 노드 중 노드 2에서 탐색을 시작)	4	2 3 5	1 4	노드 1 : 9 (7 + 2) 노드 2 : 0 (0) 노드 3 : 7 (4 + 3)  노드 4 : 4 (0 + 4) 노드 5 : 10 (4 + 6) [9, 0, 7, 4, 10]
5 (가장 거리가 먼 노드 5를 시작점으로 다시 탐색을 시작)	4	2 3 5	4 1 4	노드 1 : 11 (9 + 2) 노드 2 : 10 (6 + 4) 노드 3 : 9 (6 + 3) 노드 4 : 6 (0 + 6) 노드 5 : 0 (0) [11, 10, 9, 6 0]

슈도코드 작성하기

N(노드 개수) A(그래프 데이터 저장 인접 리스트)
visited(방문 기록 저장 배열) distance(거리 저장 배열)
for(N의 개수만큼 반복하기) {
    A 인접 리스트의 각 ArrayList 초기화하기
}
for(N의 개수만큼 반복하기) {
    A 인접 리스트에 그래프 데이터 저장하기
{
visited 배열 초기화하기
distance 배열 초기화하기
BFS(임의의 점을 시작점으로) 실행하기
distance 배열에서 가장 큰 값을 지니고 있는 노드를 시작점으로 지정하기
visited 배열 초기화하기
distance 배열 초기화하기
BFS(새로운 시작점으로) 실행하기
distance 배열에서 가장 큰 수를 정답으로 출력하기

BFS {
    큐 자료구조에 시작 노드 삽입하기
    visited 배열에 현재 노드 방문 기록하기
    while(큐가 비어 있을 때까지) {
        큐에 노드 데이터를 가져오기
        현재 노드의 연결 노드 중 방문하지 않은 노드로
        큐에 데이터 삽입하고 visited 배열에 방문 기록하기
        현재 노드의 거리 + 엣지의 가중치로 방문하지 않은 노드 거리 배열 업데이트하기
    }
}
Edge {
    e(목적지 노드), value(엣지의 가중치)
}

코드 구현하기

/**
 * 1167) 트리의_지름
 */
public class D028_1167 {
    // visited(방문 기록 저장 배열)
    static boolean visited[];
    // distance(거리 저장 배열)
    static int[] distance;
    // A(그래프 데이터 저장 인접 리스트)
    static ArrayList<Edge>[] A;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(노드 개수)
        int N = sc.nextInt();
        // A 인접 리스트의 각 ArrayList 초기화하기
        A = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            A[i] = new ArrayList<Edge>();
        }
        // A 인접 리스트에 그래프 데이터 저장하기
        for (int i = 0; i < N; i++) {
            int S = sc.nextInt();
            while (true) {
                int E = sc.nextInt();
                if (E == -1)
                    break;
                int V = sc.nextInt();
                A[S].add(new Edge(E, V));
            }
        }
        // visited 배열 초기화하기
        visited = new boolean[N + 1];
        // distance 배열 초기화하기
        distance = new int[N + 1];
        // BFS(임의의 점을 시작점으로) 실행하기
        BFS(1);
        // distance 배열에서 가장 큰 값을 지니고 있는 노드를 시작점으로 지정하기
        int Max = 1;
        for (int i = 2; i <= N; i++) {
            if (distance[Max] < distance[i])
                Max = i;
        }
        // visited 배열 초기화하기
        visited = new boolean[N + 1];
        // distance 배열 초기화하기
        distance = new int[N + 1];
        // BFS(새로운 시작점으로) 실행하기
        BFS(Max);
        // distance 배열에서 가장 큰 수를 정답으로 출력하기
        Arrays.sort(distance);
        System.out.println(distance[N]);
    }

    public static void BFS(int index) {
        Queue<Integer> queue = new LinkedList<Integer>();
        // 큐 자료구조에 시작 노드 삽입하기
        queue.add(index);
        // visited 배열에 현재 노드 방문 기록하기
        visited[index] = true;
        while (!queue.isEmpty()) {
            // 큐에 노드 데이터를 가져오기
            int now = queue.poll();
            // 현재 노드의 연결 노드 중 방문하지 않은 노드로
            for (Edge i : A[now]) {
                int e = i.e;
                int v = i.value;
                // 큐에 데이터 삽입하고 visited 배열에 방문 기록하기
                if (!visited[e]) {
                    visited[e] = true;
                    queue.add(e);
                    // 현재 노드의 거리 + 엣지의 가중치로 방문하지 않은 노드 거리 배열 업데이트하기
                    distance[e] = distance[now] + v;
                }
            }
        }
    }
}

class Edge {
    // e(목적지 노드)
    int e;
    // value(엣지의 가중치)
    int value;

    public Edge(int e, int value) {
        this.e = e;
        this.value = value;
    }
}