[프로그래머스/JAVA] 49189번 가장 먼 노드 (그래프, BFS)

문제

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

 

 

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다.

1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다.

가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

 

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때,

1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

 

 

제한 사항

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

 

 

입출력 예시

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

 

 

문제 풀이

접근 방법

• 그래프의 간선간의 가중치가 동일하다.
• 음의 가중치가 존재하지 않는다.
• 1번 노드에서 시작해서 모든 노드간의 거리를 계산한다.
  • 다익스트라 알고리즘, BFS 를 사용한다.
  • 거리 배열을 만든 후 모든 거리를 무한으로 초기화한다.
  • 1번 노드에서 인접한 노드를 탐색해서 거쳐가는 거리가 더 짧을 경우 거리를 갱신한다.
  • 이 과정을 반복하여 1번 노드로 부터 모든 노드간의 거리를 찾는다.
• 최대 거리인 노드가 몇 개 인지 반환한다.

 

코드

import java.util.LinkedList;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class P_49189 {

    private static int solution(int n, int[][] edge) {

        Map<Integer, List<Integer>> graph = new HashMap<>();

        for (int i=1; i<=n; i++) {
            graph.put(i, new ArrayList<>());
        }

        for (int[] input : edge) {
            graph.get(input[0]).add(input[1]);
            graph.get(input[1]).add(input[0]);
        }

        int max = 0;
        int count = 0;

        // 1번 노드에서 시작하는 모든 노드의 거리 계산
        int[] distances = bfs(n, 1, graph);

        // 최대 거리와 동일한 노드 개수 세기
        for (int i = 1; i <= n; i++) {
            if (max < distances[i]) {
                max = distances[i];
                count = 1;
            } else if (max == distances[i]) {
                count++;
            }
        }

        return count;
    }


    private static int[] bfs(int n, int start, Map<Integer, List<Integer>> graph) {

        // 모든 거리를 무한으로 초기화후, 시작 노드 거리 0으로 설정
        int[] distance = new int[n + 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;

        // 큐에 시작 노드 추가
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            // 현재 노드의 인접 노드
            for (int neighbor : graph.get(current)) {
                // 직접 가는 거리보다 current 노드를 거쳐 가는 거리가 짧다면 업데이트후 큐에 추가
                if (distance[current] + 1 < distance[neighbor]) {
                    distance[neighbor] = distance[current] + 1;
                    queue.add(neighbor);
                }
            }
        }
        return distance;
    }
}