[BFS] 백준 1167번 (트리의 지름)

문제

트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.
먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.

 

 

문제분석

트리의 지름 구하기
- 트리의 지름을 구하려면, 임의의 노드에서 가장 먼 노드를 탐색
- 탐색된 노드에서 가장 긴 노드와의 거리가 트리의 지름

• 그림에서 보면, 각 노드에서 가장 먼거리에 있는 노드가 트리의 지름의 두개의 노드 중 한개를 가리키게 된다.
  • ex)
    • B에서 가장 긴 노드는 U
    • 트리의 지름은 그림과 같이 "AU"이므로 U를 가리키게됨

[BFS풀이]
- 방문 배열, 거리 배열, 노드 클래스, BFS 작업을 이용하여, 방문하지 않은 노드의 최대 거리를 구하면된다

 

슈도코드

N(노드 개수)
visited(방문 배열 초기화) , distance(거리 배열 초기화)
arr(노드 초기화)

for(노드 개수만큼){
    연결 노드 저장
}

bfs(임의의점)
maxDistanceIndex (거리의 최대인 지점의 노드 인덱스)
visited(방문배열 초기화) , distance(거리 배열 초기화)

bfs(거리 최대 지점의 노드 인덱스)

최대거리 출력



노드 클래스 (노드인덱스, 거리값)

bfs(인덱스){
    queue(인덱스 삽입)
    visited(인덱스 방문 등록)
    
    while(큐가 빌때까지){
        다음 노드 연결을 위한 노드 꺼내기
        
        if(방문하지 않았다면){
            거리 배열 저장(노드별 거리 누적값)
            queue 삽입
            방문 저장
         }
     }
}

maxDistanceIndex(거리 배열){
    max 값 추출 -> 해당 인덱스 반환
}

 

구현

import java.util.StringTokenizer;
import java.util.Queue;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;

public class App {
    
    private static ArrayList<Node>[] arr;
    private static boolean[] visited;
    private static int[] distance;
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int nodeSize = Integer.parseInt(bf.readLine())+1;

        arr = new ArrayList[nodeSize];
        for(int i =0; i<nodeSize; i++){
            arr[i] = new ArrayList<>();
        }

        visited = new boolean[nodeSize];
        distance = new int[nodeSize];


        for(int i =1; i<nodeSize; i++){
            StringTokenizer st = new StringTokenizer(bf.readLine());
            int nodeNum = Integer.parseInt(st.nextToken());
            while(st.hasMoreTokens()){
                int connectedNode = Integer.parseInt(st.nextToken());
                if (connectedNode == -1) break; // 연결 종료 조건
                int weight = Integer.parseInt(st.nextToken());
                arr[nodeNum].add(new Node(connectedNode, weight));
            }
        }
  
        bfs(1);
        int maxIndex = maxDistanceIndex(distance);

        for(int i =0; i<nodeSize; i++){
            visited[i] = false;
            distance[i] = 0;
        }

        bfs(maxIndex);
        maxIndex = maxDistanceIndex(distance);
        System.out.println(distance[maxIndex]);
        

    }

    private static void bfs(int index){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(index);
        visited[index] = true;

        while(!queue.isEmpty()){
            int exitNode = queue.poll();
            for(Node node :arr[exitNode]){
                if (!visited[node.getNodeNum()]){
                    queue.add(node.getNodeNum());
                    visited[node.getNodeNum()] = true;
                    distance[node.getNodeNum()] =distance[exitNode] + node.getDistance();
                }
            }
        }

    }

    private static int maxDistanceIndex(int[] distance){
        int max = 0;
        int maxIndex = 0;
        for (int i =1; i<distance.length; i++){
            if(max > distance[i]){
                continue;
            }else{
                max = distance[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }


    public static class Node{
        public Integer nodeNum;
        public Integer distance;

        public Node(){}

        public Node(Integer nodeNum, Integer distance){
            this.nodeNum = nodeNum;
            this.distance = distance;
        }
        public Integer getNodeNum(){
            return this.nodeNum;
        }
        public void setNodeNum(Integer num){
            this.nodeNum = num;
        }

        public Integer getDistance(){
            return this.distance;
        }

        public void setDistance(Integer num){
            this.distance = num;
        }
    }
}