가장 먼 노드 (Java)

📌 문제 설명

가장 먼 노드 - 프로그래머스

• n개의 노드로 이루어진 양방향 그래프가 주어진다.
• 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 문제.

---

💡 접근 방식

이 문제는 그래프에서 1번 노드로부터 가장 먼 거리의 노드 개수를 구하는 문제이므로
BFS(너비 우선 탐색)를 사용하여 최단 거리를 구하는 방식이 적절합니다.

✔ BFS는 최단 경로를 구할 때 효과적
✔ 1번 노드에서 시작하여 레벨 단위로 탐색
✔ 가장 멀리 떨어진 거리의 노드 개수를 세면 정답!

---

🔹 BFS 탐색 과정

1. 그래프 구성
   • List<Integer>[] connInfo를 사용하여 양방향 연결 정보 저장
2. BFS 탐색
   • Queue<int[]>를 사용하여 (노드 번호, 현재 거리) 정보를 저장
   • visited[] 배열을 사용하여 방문 여부 체크
   • 각 노드까지의 거리를 cntArr[] 배열에 저장
3. 결과 계산
   • cntArr[]에서 가장 큰 거리 값을 찾고, 그 거리와 동일한 노드 개수를 반환

---

📝 코드 구현

import java.util.*;

class Solution {
    List<Integer>[] connInfo; // 그래프 연결 정보
    int N; // 노드 개수
    int[] cntArr; // 각 노드까지의 거리 저장 배열
    
    public int solution(int n, int[][] edge) {
        N = n + 1;
        cntArr = new int[N];

        // 그래프 초기화
        connInfo = new List[N];
        for (int i = 0; i < N; i++) {
            connInfo[i] = new ArrayList<>();
        }

        // 양방향 그래프 저장
        for (int[] e : edge) {
            connInfo[e[0]].add(e[1]);
            connInfo[e[1]].add(e[0]);
        }

        // BFS 실행 (1번 노드부터)
        int maxDistance = bfs(1);

        // 가장 먼 거리(maxDistance)와 같은 노드 개수 계산
        int answer = 0;
        for (int i = 1; i < N; i++) {
            if (cntArr[i] == maxDistance) answer++;
        }
        return answer;
    }
    
    private int bfs(int start) {
        int maxDistance = 0;
        boolean[] visited = new boolean[N];
        Queue<int[]> queue = new LinkedList<>();
        
        visited[start] = true;
        queue.add(new int[]{start, 0}); // (노드번호, 현재 거리)
        
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int curNode = cur[0];
            int curDist = cur[1];

            for (int nextNode : connInfo[curNode]) {
                if (visited[nextNode]) continue;

                visited[nextNode] = true;
                cntArr[nextNode] = curDist + 1; // 거리 갱신
                maxDistance = Math.max(maxDistance, cntArr[nextNode]);
                queue.add(new int[]{nextNode, curDist + 1});
            }
        }
        return maxDistance;
    }
}

---

🧐 코드 분석

변수	의미
connInfo	노드 연결 정보를 저장하는 리스트 배열
cntArr	각 노드까지의 최단 거리 저장 배열
visited	방문 여부를 저장하는 배열
Queue<int[]>	BFS를 위한 큐 (노드번호, 거리)

🔹 시간복잡도

• BFS의 시간 복잡도: O(V + E) (V: 노드 개수, E: 간선 개수)
• 각 노드는 한 번씩 방문하며, 연결된 간선만큼 탐색하므로 최적의 성능을 보장

---

🎯 예제 실행

입력 예시

int n = 6;
int[][] edge = {
    {3, 6}, {4, 3}, {3, 2}, {1, 3}, 
    {1, 2}, {2, 4}, {5, 2}
};

BFS 탐색 과정

탐색 단계	방문 노드	큐 상태
1	1(0)	{2, 3}
2	2(1)	{3, 4, 5}
3	3(1)	{4, 5, 6}
4	4(2)	{5, 6}
5	5(2)	{6}
6	6(3)	{}

결과
가장 먼 거리: 3
해당 거리의 노드 개수: 1

✅ 출력값: 1

---

🚀 결론 및 정리

✔ BFS를 활용하여 그래프에서 최단 거리를 계산
✔ 가장 먼 거리 값을 찾고 해당 노드 개수를 반환
✔ 시간 복잡도 O(V + E), 최적의 그래프 탐색 알고리즘 사용