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

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   n개의 노드가 있는 그래프가 있을 때, 각 노드는 1부터 n까지 번호가 적혀있다. 1번 노드에서 가장 멀리 떨어진(최단경로로 이동했을 때 간선의 개수가 가장 많은) 노드의 개수를 구하는 문제이다.

   노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 주어진다. 제한 사항은 다음과 같다.

 

• 2 ≤ n ≤ 20,000
• 1 ≤ 간선의 수 ≤ 50,000
• 간선은 양방향이다.
• vertex [a, b]는 a번 노드와 b번 노드에 간선이 있다는 의미이다.

---

접근 방식

   BFS의 개념을 이용해 문제를 해결하였다. 핵심은 재방문을 방지해야 하고 탐색하려는 노드의 범위를 명확히하는 것이다. 예제를 통해 알아보자.

 

 

   시작 지점은 항상 1번 노드부터이다. 1번 노드와 연결된 노드는 다음과 같이 2번, 4번, 5번 노드를 찾을 수 있다.

 

 

   이제 찾은 2번, 4번, 5번 노드와 연결된 노드들을 찾아보자. 다음과 같이 3번, 5번 노드를 찾을 수 있다.

 

 

   2번 노드와 5번 노드에 연결된 노드를 찾는 과정에서 4번 노드를 다시 방문하게 되는 경우가 있다. 이 경우 4번 노드에 대한 방문 여부를 체크해두지 않은 경우 중복 탐색이 발생하여 무한 루프가 발생할 수 있으니 주의해야 한다.

 

 

   과정을 정리해보면 처음에 1번 노드에서 시작하여 최단 경로가 1인 노드들을 찾았고 2번, 4번, 5번 노드가 이에 해당한다. 그 다음 찾은 노드들에 대해 탐색을 진행한 결과 3번, 5번 노드를 찾았으며 해당 노드들이 1번 노드로부터 가장 먼 노드이므로 답은 2를 반환하게 된다.

   주목할 점은 최단 경로가 1씩 증가하며 탐색 범위를 제한했다는 점이다. 즉, BFS를 진행할 때 기존에 있던 노드와 새로 들어온 노드를 구분해야 한다.

 

 

   가장 먼 노드들의 수에 대해서도 생각해보자. 처음 탐색할 대상은 1번 노드로 limit의 수는 1개이다. 그 다음 탐색에선 3개의 노드가 탐색 대상이 되며 limit의 수는 3이다. 마지막 탐색에선 limit가 2이며 탐색으로 새로 찾는 노드가 존재하지 않는다. 가장 먼 노드의 수는 2가 된다.

   그렇다면 3번 노드에 추가로 새로운 노드가 붙는다고 가정해보자. 3번과 6번 노드의 탐색이 종료되고 새로 추가된 7번 노드에 대한 탐색이 진행되야 한다. 이때 limit의 수는 1이며 가장 먼 노드는 7번 노드로 답은 1이 된다. 이 점에서 알 수 있는 것은 탐색 시에 새로 발견된 노드가 없다면 해당 노드는 가장 먼 노드이며, 이번 탐색의 대상이 된 노드들의 수가 가장 먼 노드들의 수임을 의미한다.

 

---

코드

import java.util.*;

public class 프로그래머스49189번 {
    public int solution(int n, int[][] edge) {
        List<Integer>[] link = new List[n + 1];

        for (int i = 1; i <= n; i++)
            link[i] = new LinkedList<>();
        //연결관계를 양방향으로 저장
        for (int[] e : edge) {
            link[e[0]].add(e[1]);
            link[e[1]].add(e[0]);
        }
        return BFS(link);
    }

    public int BFS(List<Integer>[] link) {
        Queue<Integer> q = new ArrayDeque<>();
        //재방문 방지를 위한 방문 배열
        boolean[] visited = new boolean[link.length];
        int count = 0;

        //시작 노드는 1번 노드
        q.add(1);
        visited[1] = true;
        while (!q.isEmpty()) {
            count = q.size();
            //현재 저장된 노드에 대해서만 탐색을 진행
            for (int l = 0; l < count; l++) {
                int cur = q.poll();
                //현재 노드와 연결된 노드만 유효성을 판단하여 큐에 저장(저장된 노드는 다음 탐색의 대상이 됨)
                for (int next : link[cur]) {
                    if (visited[next]) continue;
                    visited[next] = true;
                    q.add(next);
                }
            }
        }
        //가장 먼 노드란 더 이상 탐색의 대상이 없는 경우를 의미
        return count;
    }
}