[백준 JAVA] 1167 : 트리의 지름

[백준 1167] 트리의 지름 : https://www.acmicpc.net/problem/1167

1167번: 트리의 지름

---

문제 조건 정리

 

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

 

---

입력

 

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

---

문제를 풀기 전

 

1. bfs를 통해서 첫 번째 노드부터 n 번째 노드까지 모두 bfs를 해서 최장 거리, 즉 지름을알아내야 한다고 생각했음!
2. 생각해보니 간선에 가중치도 있음! 다익스트라로 풀어야할까 고민해봄!
3. 최단 경로가 아닌 최장 경로, 그리고 사이클이 없는 트리라는 키워드에서 해당 문제는 bfs로 풀 수 있지 않을까? 라고 생각함!
4. 조심스러워서 트리의 지름을 구하는 방법에 대해서 알아봄!
5. 트리의 지름은 임의의 노드에서부터 가장 먼 노드를 찾아내고 해당 노드에서 가장 먼 노드까지의 거리라는 것을 배움!
6. 이는 bfs로 가능하다고 확신함!

---

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    // 간선을 정의하는 클래스
    private static class Edge {
        int target, distance;

        public Edge(int target, int distance) {
            this.target = target;
            this.distance = distance;
        }
    }

    // 노드의 상태를 정의하는 클래스
    private static class NodeState {
    
        // 현재 노드의 위치
        int currentPosition;
        
        // 시작 지점으로부터 누적된 거리
        int accumulatedDistance; 

        public NodeState(int currentPosition, int accumulatedDistance) {
            this.currentPosition = currentPosition;
            this.accumulatedDistance = accumulatedDistance;
        }
    }

    // 입력되는 노드의 개수
    static int n;
    
    // 노드들의 간선들을 저장하는 리스트
    // 노드의 개수가 주어지므로 배열안에 리스트를 선언해도 무방함
    static List<List<Edge>> adjList;

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(bufferedReader.readLine());

        adjList = new ArrayList<>();

        // 인접 리스트 초기화
        for (int i = 0; i <= n; i++) {
            adjList.add(new ArrayList<>());
        }

        // 인접 리스트 채우기
        for (int i = 1; i <= n; i++) {
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");

            // 특정 노드
            int current = Integer.parseInt(stringTokenizer.nextToken());

            while (true) {
            
                // 타겟 노드
                int node = Integer.parseInt(stringTokenizer.nextToken());
                
                // 종료 조건
                if (node == -1) {
                    break;
                }
                
                // 타겟 노드까지의 거리
                int dist = Integer.parseInt(stringTokenizer.nextToken());
                
                // 인접 리스트의 특정 노드에 타겟 노드까지의 간선 정보를 추가
                adjList.get(current).add(new Edge(node, dist));
            }
        }

        // 임의의 노드(1)로 부터 가장 먼 노드를 찾기
        NodeState foundNode = bfs(1);
        
        // 위에서 찾은 노드에서부터 가장 먼 노드를 찾기 -> 트리 지름
        NodeState resNode = bfs(foundNode.currentPosition);
        
        // 트리 지름 출력
        System.out.println(resNode.accumulatedDistance);

    }

    // 출발 노드를 받고 bfs 알고리즘을 진행하는 메서드
    private static NodeState bfs(int startNode) {
    
        Queue<NodeState> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[n + 1];
        
        // 큐에 출발 노드를 삽입, 방문 처리
        queue.offer(new NodeState(startNode, 0));
        visited[startNode] = true;

        // 가장 먼 노드를 저장할 객체 초기화
        NodeState farthestNode = new NodeState(-1, -1);

        while (!queue.isEmpty()) {
            NodeState current = queue.poll();

            // 큐에서 꺼낸 노드의 인접한 간선들을 추출
            List<Edge> edges = adjList.get(current.currentPosition);
            
            for (Edge edge : edges) {
                
                // 방문하지 않은 노드라면
                if (!visited[edge.target]) {
                    visited[edge.target] = true;
                    
                    // 해당 간선을 지나간 노드의 상태를 선언하고 큐에 추가
                    NodeState nextNode = new NodeState(edge.target, current.accumulatedDistance + edge.distance);
                    queue.offer(nextNode);
                    
                    // 출발 노드에서부터 가장 먼 노드로 설정한 노드보다
                    // 방금 계산한 노드가 더 멀다면 덮어씌움
                    if (farthestNode.accumulatedDistance < nextNode.accumulatedDistance) {
                        farthestNode = nextNode;
                    }
                }
            }
        }

        // 큐가 비었다면 bfs 종료
        // 가장 먼 노드를 반환함
        return farthestNode;
    }
}

 

---

문제를 풀고 난 후

 

풀다보니 dfs가 더 효율적일 것 같다는 생각이 들었음!

"다익스트라로 풀까?" 헷갈렸던 것 때문에 dfs는 염두에 두지 않았음!

 

이번 문제는 입력때문에 고생했음!

노드의 개수가 3개라면 1,2,3 순서로 주어지는 것이 아니라 3,1,2 순서로 주어질 수도 있었음!

 

그래서 인접 리스트를 초기화 하지 않았던 나는 인덱스 아웃 오브 바인드 오류를 보고 당황함!

(리스트는 인덱스가 하나씩 오름차순으로 증가해야함! -> 2번 인덱스를 초기화하지 않고 3번 인덱스에 값을 초기화 할 수 없음)

 

역시 입력 값을 잘 활용해야겠다고 생각함!