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

문제

 

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

 

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

 

 

제한 사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

 

---

풀이

 

내가 좋아하는 그래프 문제이다. 다른 Level 3 문제와 다르게 좀 쉽게 느껴졌다. 이번 문제는 넓이 우선 탐색(BFS, Breadth First Search)을 사용해서 풀 수 있었다.

 

 

1번 노드에서 시작해서 가장 멀리 떨어진 노드의 개수를 구하는 문제다.

 

먼저, 인접한 노드들을 따로 저장해 둔다.

ex) 주어지는 노드 정보가 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]일 때,

인접 노드는 [[], [3, 2], [3, 1, 4, 5], [6, 4, 2, 1], [3, 2], [2], [3]]이 된다. 해석하자면

1번 노드에는 3, 2번 노드가 연결되어 있다.
2번 노드에는 3, 1, 4, 5번 노드가 연결되어 있다.
3번 노드에는 6, 4, 2, 1번 노드가 연결되어 있다.
...
6번 노드에는 3번 노드가 연결되어 있다.

 

1번 노드부터 연결된 노드들을 따라 가면서 1씩 더해주면 가장 먼 노드를 구할 수 있다.

dist[next] = dist[now] + 1

ex) now = 1일 때(현재 노드가 1번 노드일 때), next는 3, 2번 노드이다. 즉,

1번 노드에서 3, 2번노드로 갈 때 1을 더해준다. 

 

이러면 가장 먼 노드를 구할 수 있고, 가장 먼 노드의 개수를 세면 된다.

 

import java.util.*;

public class Solution {
    private List<List<Integer>> graph = new ArrayList<>();
    private int[] dist;
    private int max = 0;

    private void bfs(int v) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(v);
        dist[v] = 1;

        while(!q.isEmpty()) {
            int now = q.poll();

            for(int next : graph.get(now)) {
                if(dist[next] == 0) {
                    dist[next] = dist[now] + 1;
                    q.offer(next);
                    max = Math.max(max, dist[next]);
                }
            }
        }
    }

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

        dist = new int[n+1];

        for(int i=0; i<=n; i++) graph.add(new ArrayList<>());
        for(int[] e : edge) {
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }

        bfs(1);

        for(int d : dist) {
            if(d == max) answer++;
        }

        return answer;
    }
}