[코딩테스트] 백준 1167 자바

백준 1167

백준 1167 문제

해당 문제는 주어진 트리의 지름(가장 긴 거리)를 구하는 문제이다.

임의의 노드를 기준으로 가장 긴 노드는 BFS를 통해 구할 수 있는데, 이렇게 구한 노드는 트리의 지름을 구성하는 두 노드 중 하나이다.

따라서, 임의의 노드에서 가장 긴 노드를 기준으로 다시 한번 BFS를 통해 가장 긴 노드까지의 거리를 구하면 트리의 지름을 알 수 있다.

import java.util.*;

public class Boj1167 {

    private static boolean[] visited;
    private static int[] distance;
    private static List<Node>[] edgeList;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 노드 개수
        edgeList = new ArrayList[n + 1]; // 그래프 데이터 저장 인접 리스트

        for (int i = 1; i <= n; i++) {
            edgeList[i] = new ArrayList<>(); // 인접 리스트에 각 ArrayList 초기화
        }

        // 인접 리스트에 그래프 데이터 저장
        for (int i = 0; i < n; i++) {
            int s = sc.nextInt();

            while (true) {
                int e = sc.nextInt();

                if (e == -1) {
                    break;
                }

                int v = sc.nextInt();
                edgeList[s].add(new Node(e, v));
            }
        }

        distance = new int[n + 1]; // 거리 배열 초기화
        visited = new boolean[n + 1]; // 방문 기록 배열 초기화

        bfs(1); // 임의 노드를 시작점으로 bfs 실행

        int max = 1;

        // 거리 배열에서 가장 큰 값을 지니고 있는 노드를 시작점으로 저장
        for (int i = 2; i <= n; i++) {
            if (distance[max] < distance[i]) {
                max = i;
            }
        }

        distance = new int[n + 1]; // 거리 배열 초기화
        visited = new boolean[n + 1]; // 방문 기록 배열 초기화

        bfs(max); // 거리 배열에서 가장 큰 값을 지니고 있는 노드를 시작점으로 bfs 실행

        Arrays.sort(distance); // 거리 배열 오름차순 정렬

        System.out.println(distance[n]); // 거리 배열에서 가장 큰 수 출력
    }

    private static void bfs(int index) {
        Queue<Integer> queue = new LinkedList<>(); // 큐 자료구조 생성
        queue.offer(index); // 큐에 시작 노드 삽입
        visited[index] = true; // 현재 노드 방문 기록

        while (!queue.isEmpty()) { // 큐가 비어 있을 때까지 반복
            int now = queue.poll(); // 큐에서 노드 데이터 꺼내기

            for (Node n : edgeList[now]) { // 현재 노드의 연결 노드 중
                int next = n.next;
                int value = n.value;

                if (!visited[next]) { // 방문하지 않은 노드는
                    visited[next] = true; // 방문 기록
                    queue.add(next); // 큐에 데이터 삽입
                    distance[next] = distance[now] + value; // 현재 노드의 거리 + 에지의 가중치로 방문하지 않은 노드 거리 배열 업데이트
                }
            }
        }
    }

    // 노드 클래스 구현
    static class Node {
        int next; // 목적지 노드
        int value; // 에지의 가중치

        public Node(int next, int value) {
            this.next = next;
            this.value = value;
        }
    }
}

문제 풀이

1. 노드 개수를 n에 저장한다.
2. 그래프 데이터 저장 인접 리스트 edgeList를 생성한다.
   2-1. 해당 트리의 노드들은 가중치를 지니고 있기 때문에 인덱스와 가중치를 가지는 Node 클래스를 가지는 인접 리스트를 생성한다.
3. edgeList에 각 ArrayList를 초기화한다.
4. edgeList에 그래프 데이터를 저장한다.
5. 거리 배열 distance를 초기화한다.
6. 방문 기록 배열 visited를 초기화한다.
7. 임의 노드를 시작점으로 bfs()를 실행한다.
   7-1. Queue 자료구조를 생성한다.
   7-2. 큐에 시작 노드를 삽입한다.
   7-3. 현재 노드에 방문 기록을 한다.
   7-4. 큐가 비어있을 때까지 반복한다.
   • 7-4-1. 큐에서 노드 데이터 now를 꺼낸다.
   • 7-4-2. 꺼낸 노드의 연결 노드들 중 방문하지 않은 노드 next는 방문 기록한다.
   • 7-4-3. 큐에 next를 삽입한다.
   • 7-4-4. 꺼낸 노드(now)의 거리 + 에지의 가중치(value)로 방문하지 않은 노드(next) 거리 배열dmf 업데이트한다.
8. distance에서 가장 큰 값을 지니고 있는 노드를 시작점(max)로 저장한다.
9. 거리 배열 distance를 초기화한다.
10. 방문 기록 배열 visited를 초기화한다.
11. distance 배열에서 가장 큰 값(max)을 지니고 있는 노드를 시작점으로 bfs()를 실행한다.
12. 7-1 과정을 수행한다.
13. distance 배열을 오름차순으로 정렬한다.
14. distance에서 가장 큰 수를 출력한다.