BaekJoon 1167 트리의 지름

트리의 지름을 구하는 문제입니다.

https://www.acmicpc.net/problem/1167

트리의 지름을 구하는 방법은 bfs를 2번 돌리면 구할 수 있다고 합니다.

1. 임의의 node에서 bfs를 실행하여 가장 거리가 긴 node를 구합니다.

2. 가장 거리가 먼 node에서 다시 bfs를 실행하여 가장 거리가 먼 node까지의 거리를 구합니다.

어째서 위의 2단계를 거치면 트리의 지름을 구할 수 있는 것 일까요?
일단 임의의 점(u)에서 가장 먼 node(v)라고 했을 때, 다음과 같은 경우가 발생합니다.

1. u가 root이면 v는 제일 먼 leaf node가 됩니다.

2. u가 root가 아니라면 u, v의 경로 사이에는 root가 존재하고, v는 leaf node가 됩니다.

1번이든 2번이든 v는 root에서 가장 먼 leaf node가되고, bfs를 한번 더 실행하면 root에서 v까지의 거리 다음으로 작거나 같은 노드가 선택됩니다. 따라서 트리의 지름을 구할 수 있는 것입니다.

코드는 다음과 같습니다.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
import java.util.Stack;

public class BaekJoon1167 {
    static int V, u, v, w, max, maxIndex;
    static boolean[] visit = new boolean[100001];
    static HashMap<Integer, Integer>[] hm = new HashMap[100001];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        V = sc.nextInt();
        for (int i = 1; i <= V; i++) {
            hm[i] = new HashMap<>();
        }

        for (int i = 1; i <= V; i++) {
            u = sc.nextInt();
            while (true) {
                v = sc.nextInt();
                if (v == -1) break;
                w = sc.nextInt();
                hm[u].put(v, w);
            }
        }
        dfs(1);dfs(maxIndex);
        System.out.println(max);
    }
    public static int dfs(int v)  {
        Arrays.fill(visit, false);
        Stack<Edge> s = new Stack<>();
        max = 0;maxIndex = 1;s.push(new Edge(v, 0));
        visit[v] = true;
        while (!s.isEmpty()) {
            Edge curNode = s.pop();
            if (max < curNode.w) {
                max = curNode.w; maxIndex = curNode.v;
            }
            for (int key : hm[curNode.v].keySet()) {
                Edge e = new Edge(key, hm[curNode.v].get(key));
                if (!visit[e.v]) {
                    visit[e.v] = true; s.push(new Edge(e.v, e.w + curNode.w));
                }
            }
        }
        return max;
    }
    private static class Edge {
        int v, w;
        Edge(int v, int w) {
            this.v = v; this.w = w;
        }
    }
}

이 블로그 검색

Do.

BaekJoon 1167 트리의 지름

이 블로그의 인기 게시물

웹툰 무료로 볼 수 있는 사이트

BackJoon 1011, Fly me to the alpha centauri, 규칙 찾기 문제

BaekJoon 6591, 이항 쇼다운 조합문제