백준 1167번 트리의 지름

문제

나의 풀이

import java.util.*;

public class Main {
    static class Edge {
        public int to;
        public int cost;
        Edge(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }
    }
    public static int[] bfs(int n, List<Edge>[] a, int start) {
        boolean check[] = new boolean[n + 1];
        int dist[] = new int[n + 1];
        Queue<Integer> q = new LinkedList<Integer>();
        check[start] = true;
        q.add(start);
        while(!q.isEmpty()) {
            int x = q.poll();
            for(Edge e : a[x]) {
                int y = e.to;
                int cost = e.cost;
                if(check[y] == false) {
                    dist[y] = dist[x] + cost;
                    q.add(y);
                    check[y] = true;
                }
            }
        }
        return dist;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Edge>[] a = (List<Edge>[]) new List[n + 1];
        for(int i = 1; i <= n; i++) {
            a[i] = new ArrayList<Edge>();
        }
        for(int i = 1; i <= n; i++) {
            int x = sc.nextInt();
            while(true) {
                int y = sc.nextInt();
                if(y == -1) {
                    break;
                }
                int z = sc.nextInt();
                a[x].add(new Edge(y, z));
            }
        }
        int dist[] = bfs(n, a, 1);
        int start = 1;
        for(int i = 2; i <= n; i++) {
            if(dist[i] > dist[start]) {
                start = i; // 가장 거리가 먼 정점 찾기
            }
        }
        
        dist = bfs(n, a, start); // 가장 거리가 멀었던 정점을 시작점으로 bfs 탐색
        int answer = dist[1];
        for(int i = 2; i <= n; i++) {
            if(answer < dist[i]) {
                answer = dist[i];
            }
        }
        System.out.println(answer);
    }
}

트리의 지름은 탐색 2번으로 구할 수 있다. 한 정점 s에서 모든 정점까지의 거리를 구한다. 이때, 가장 먼거리인 정점은 u라고 한다. u에서 모든 정점까지의 거리를 구한다. 이때 가장 먼 거리인 정점 v를 구한다. u와 v사이의 거리가 트리의 지름이다.
즉, 한 정점 s에서 BFS 탐색을 시작해서 가장 거리가 멀었던 정점을 x라고 하고 x에서 BFS 탐색을 시작해서 가장 거리가 멀었던 정점을 y라고 하여 x와 y의 거리를 구해주면 된다.

결과

백준 1967번 트리의 지름

문제

나의 풀이

import java.util.*;

public class Main {
    static class Edge {
        int to, cost;
        Edge(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }
    }
    static ArrayList<Edge>[] a;
    static boolean[] check = new boolean[10001];
    static int[] dist = new int[10001];
    static void bfs(int start) {
        Arrays.fill(dist, 0);
        Arrays.fill(check, false);
        Queue<Integer> q = new LinkedList<>();
        check[start] = true;
        q.add(start);
        while(!q.isEmpty()) {
            int x = q.poll();
            for(Edge e : a[x]) {
                if(check[e.to] == false) {
                    dist[e.to] = dist[x] + e.cost;
                    q.add(e.to);
                    check[e.to] = true;
                }
            } 
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        a = (ArrayList<Edge>[]) new ArrayList[n + 1];
        for(int i = 1; i <= n; i++) {
            a[i] = new ArrayList<Edge>();
        }
        for(int i = 0; i < n - 1; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            a[u].add(new Edge(v, w));
            a[v].add(new Edge(u, w));
        }
        bfs(1);
        int start = 1;
        for(int i = 2; i <= n; i++) {
            if(dist[i] > dist[start]) {
                start = i;
            }
        }
        
        bfs(start);
        int answer = dist[1];
        for(int i = 2; i <= n; i++) {
            answer = Math.max(answer, dist[i]);
        }
        System.out.println(answer);
    }
}

앞의 문제와 똑같으나, 연결 리스트를 부모->자식, 자식->부모 양방향으로 저장해준다.

결과