프로그래머스: 가장 먼 노드(JAVA)

문제 설명

프로그래머스의 "가장 먼 노드" 문제는 다음과 같은 내용을 가지고 있습니다.

• 노드 수 n, **간선 정보 edge**가 주어집니다.
• 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구해야 합니다.
• 이때, 거리는 "최단 경로 상의 간선 수"를 의미합니다.

---

접근 방법

이 문제는 전형적인 그래프 탐색 문제입니다.
"최단 거리"를 구하는 문제이므로, BFS (너비 우선 탐색) 을 사용하는 것이 적절합니다.

BFS를 사용하는 이유

• DFS는 경로 탐색에는 적합하지만, 최단 거리 보장이 없습니다.
• BFS는 시작 노드에서 가까운 노드부터 차례로 탐색하므로, 최단 거리를 보장할 수 있습니다.

---

풀이

1. 인접 리스트를 이용해 그래프를 표현합니다.
2. 1번 노드에서 BFS를 수행하여 각 노드까지의 최단 거리를 구합니다.
3. distance 배열에서 가장 큰 값(최대 거리) 을 찾습니다.
4. 그 값과 같은 거리를 가진 노드의 개수를 셉니다.

---

코드 (Java)

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;

        // 그래프 초기화
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 정보로 양방향 연결
        for (int[] arr : edge) {
            graph.get(arr[0]).add(arr[1]);
            graph.get(arr[1]).add(arr[0]);
        }

        boolean[] visited = new boolean[n + 1];
        int[] distance = new int[n + 1];

        // BFS 시작
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        visited[1] = true;

        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (int next : graph.get(now)) {
                if (!visited[next]) {
                    visited[next] = true;
                    distance[next] = distance[now] + 1;
                    queue.offer(next);
                }
            }
        }

        // 최대 거리 계산
        int max = 0;
        for (int num : distance) {
            max = Math.max(max, num);
        }

        // 최대 거리와 같은 노드 수 카운트
        for (int num : distance) {
            if (num == max) answer++;
        }

        return answer;
    }
}

 

시간 복잡도

• 그래프 탐색 (BFS): O(N + E)