탐색 알고리즘 문제 풀어보기 4(백준 1167번 트리의 지름)

이번에는 깊이, 너비 탐색으로 푸는 마지막 문제이다. 다음부터는 다른 탐색 알고리즘인 이진 탐색을 알아보고 해당 문제를 풀어볼 것이다. 이번 문제는 트리의 지름을 구하는 아주 간단한 문제이다. 트리의 리프에서 리프까지의 거리 중 최대 거리를 찾는 문제이다. 백준 1167번이다. https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

이 문제에서는 에지의 거리가 일정하지 않고 문제에서 주어진다. 따라서 모든 노드를 탐색하면서 최장거리를 찾아야 한다. 트리의 지름을 찾기 위해서는 랜덤 한 노드에서 가장 먼 노드를 찾은 후, 그 노드에서 다시 가장 먼 노드를 찾으면 된다. 이 정도만 알아두고 자세한 증명이 필요하면 검색을 해 보자.

import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<node>[] info;
    static boolean[] visited;
    static int[] count;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int V = Integer.parseInt(br.readLine());
        info = new ArrayList[V+1];
        for(int i=1;i<=V;i++){
            info[i] = new ArrayList<node>();
        }
        for(int i=1;i<=V;i++){
            st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken());
            while(true){
                int n = Integer.parseInt(st.nextToken());
                if(n==-1) break;
                int l = Integer.parseInt(st.nextToken());
                info[num].add(new node(n, l));
            }
        }
        visited = new boolean[V+1];
        count = new int[V+1];
        BFS(1);
        int max = 0;
        int maxIndex = 0;
        for(int i=2;i<=V;i++){
            if(count[i]>max){
                max = count[i];
                maxIndex = i;
            }
        }
        visited = new boolean[V+1];
        count = new int[V+1];
        BFS(maxIndex);
        max = 0;
        for(int i=1;i<=V;i++){
            if(count[i]>max){
                max = count[i];
            }
        }
        System.out.print(max);
    }
    static void BFS(int start){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        count[start] = 0;
        visited[start] = true;
        while(!queue.isEmpty()){
            int num = queue.poll();
            for(node n:info[num]){
                if(!visited[n.getNum()]){
                    queue.offer(n.getNum());
                    visited[n.getNum()] = true;
                    count[n.getNum()] = count[num] + n.getLength();
                }
            }
        }
    }
    static class node{
        int num;
        int length;
        node(int num, int length){
            this.num = num;
            this.length = length;
        }
        int getNum(){
            return this.num;
        }
        int getLength(){
            return this.length;
        }
    }
}

노드의 간선길이도 저장해야 해서 클래스를 만들어 노드의 번호와 간선의 길이를 저장하게 하였다. 만약 클래스를 쓰고 싶지 않다면 2차원 배열로 저장하는 것도 가능하다. 먼저 트리의 정보를 저장해 준 뒤에 1번 노드에서 BFS를 해주어 1번노드에서 최대거리에 있는 노드를 찾았다. 만약 최댓값이 여러 개더라도 상관이 없다. 해당 노드들에서 결국 1번 노드로 도착할 것이고 그 이후에 최댓값이 결정되기 때문이다. 에지의 개수를 찾는 것이면 의미가 있겠지만 단순히 지름을 구할 때는 의미가 없는 정보이다. 그리고 최대 노드에서 다시 BFS를 해주어 나온 최댓값이 트리의 지름이다. 거리는 카운트 배열에 저장하였다. 이 문제는 DFS를 사용해도 상관이 없다. 어차피 특정 노드에서 모든 경우를 탐색해야 하기 때문이다.

다음 포스팅부터는 탐색의 다른 방법인 이진 탐색에 대해 알아보도록 하겠다.