[BaekJoon] #1167 트리의 지름

문제이해

이 문제는 트리와 각 노드간의 거리가 주어지고, 임의의 두 노드사이의 최장거리인 트리의 지름을 구하는 문제입니다.

문제접근

트리의 지름을 구하기 위한 핵심은 양 끝 노드를 찾아야한다는 점입니다. 문제를 풀기 위한 아이디어는 다음과 같습니다.

1. 임의의 노드에서 BFS수행
2. 첫 번째 BFS에서 가장 먼 노드로부터 다시 BFS 수행

트리의 지름을 구하기 위해서는 지름의 양 끝을 구해야 합니다.

임의의 노드에서 BFS를 수행해 해당 노드로부터 가장 먼 노드를 구하게 되면, 트리의 특성 상 지름을 이루는 두 끝점 중 하나가 될 수 밖에 없습니다.

따라서, 1번의 BFS를 통해 구한 가장 먼 노드를 시작점 삼아 BFS를 다시 수행해 해당 노드로부터의 거리 중 최장거리를 구하게 되면, 해당 거리가 트리의 지름이 됩니다.

문제풀이

처음에는 2차원 배열문제처럼 linkedList를 이용해 값과 가중치를 같이 넣어주었는데, Edge클래스를 선언하면 더 편하게 구현할 수 있습니다.

Edge 클래스

인덱스와 가중치를 함께 저장해주기 위해, Edge 클래스를 정의합니다.

BFS

BFS를 이용해 모든 노드를 순회하며 시작정점으로부터 특정 정점까지의 거리를 나타내는 distance 배열을 업데이트 해줍니다.

distance 배열을 업데이트할 때는 다익스트라처럼 직전 노드까지의 거리 + 인접 노드까지의 가중치로 계산합니다.

main

main에서는 트리를 생성해주고 BFS를 두번 호출해주면 됩니다.

point

최장거리? 임의의 노드에서 BFS수행->지름의 한 끝 2. 1에서 구한 끝점에서 BFS 수행

가중치 있는 경우에는 노드클래스 정의해서 쓰기

code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{
    // 임의의 노드에서 가장 긴 경로로 연결되어있는 노드는 트리의 지름에 해당하는 두 노드 중 하나
    static boolean visited[];
    static LinkedList<Edge> adjList[];
    static int distance[];

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int k = Integer.parseInt(br.readLine());
        StringTokenizer st;
        visited = new boolean[k+1];
        adjList = new LinkedList[k+1];
        distance = new int[k+1];
        // 엣지 추가
        for(int i=1; i<k+1 ; i++){
            adjList[i] = new LinkedList<Edge>();
        }
        for(int i=0; i<k ; i++){ // k번 입력받음
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            while(true) {
                int e = Integer.parseInt(st.nextToken());
                if(e == -1){
                    break;
                }
                int value = Integer.parseInt(st.nextToken());
                adjList[S].add(new Edge(e,value));
            }
        }

        BFS(1);
        int max =1;
        // 배열 순회해서 가장 큰 max 구하기
        for(int i=1; i<k+1; i++){
            if(distance[max]<distance[i]){
                max = i;
            }
        }
        // 배열 초기화 후, max에서 다시 BFS호출
        visited = new boolean[k+1];
        distance = new int[k+1];
        BFS(max);
        Arrays.sort(distance);
        System.out.println(distance[k]);


    }

    private static void BFS(int idx){
       Queue<Integer> q = new LinkedList<Integer>();
       q.add(idx);
       while(!q.isEmpty()){
           int nowNode = q.peek();
           q.poll();
           visited[nowNode] = true;
           for(Edge i : adjList[nowNode]){ // 인접정점 순회
               int e = i.e;
               int val = i.value; // 가중치 추출해서
               if(!visited[e]){
                   q.add(e);
                   visited[e] = true;
                   distance[e] = distance[nowNode]+val; // 거리배열 update
               }
           }
       }
    }
    static class Edge{
        int e;
        int value;
        Edge(int e, int value){
            this.e = e;
            this.value = value;
        }
    }
}