[프로그래머스] 가장 먼 노드 (BFS)

문제 소개

오늘 풀었던 프로그래머스 - 가장 먼 노드 문제를 정리합니다.

이 문제는 1번 노드를 시작점으로 해서, 가장 멀리 떨어진 노드(최단 거리 기준)의 개수를 구하는 문제입니다.
즉, BFS(너비 우선 탐색) 을 통해 그래프에서 최장 레벨에 위치한 노드 개수를 세는 문제입니다.

문제 링크: 가장 먼 노드 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 무방향 그래프를 인접 리스트로 구성
2. 1번 노드에서 BFS를 수행해, 다음 노드를 큐에 저장
3. 각 거리(깊이)별 노드 수(que.size()) 중 마지막 노드 수를 반환

---

해결 과정 및 코드

핵심 아이디어

1. BFS 탐색을 통해 1번 노드에서 같은 거리에 있는 모든 노드를 구할 수 있음
2. 탐색 도중 가장 마지막 레벨(깊이)에서 탐색된 노드들의 수가 정답

코드

시간 복잡도 :O(N + E)

• N = 노드 수 (최대 20,000), E = 간선 수 (최대 50,000)
• BFS 탐색과 인접 리스트 구성 모두 선형 시간 내 해결 가능

import java.util.*;

class Solution {
    // 그래프 노드 클래스
    class Node {
        int no;
        Node next;        
        Node (int no, Node next) {
            this.no = no;
            this.next = next;
        }
    }
    
    public int solution(int n, int[][] edge) {
        Node [] graph = new Node [n+1];
        for (int i = 0; i < edge.length; i++) {
            int from = edge[i][0];
            int to = edge[i][1];
            // 무방향 그래프
            graph[from] = new Node(to, graph[from]);
            graph[to] = new Node(from, graph[to]);
        }
        
        // bfs
        ArrayDeque<Integer> que = new ArrayDeque<>();
        boolean[] visited = new boolean[n+1];
        que.offer(1);
        visited[1] = true;
        int countAtMaxDepth = 1;
        while(!que.isEmpty()) {
            countAtMaxDepth = que.size(); // 현재 깊이의 노드 수 저장
            for (int size = que.size(); size > 0; size--) {
                int cur = que.poll();
                for (Node temp = graph[cur]; temp != null; temp = temp.next) {
                    if (visited[temp.no]) continue;
                    visited[temp.no] = true;
                    que.offer(temp.no);
                }
                
            }
        }
        return countAtMaxDepth;
    }
}