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

programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

 

문제 요약

 여러 개의 노드가 이어진 그래프가 있다. 노드의 개수 n과 간선을 담고 있는 이차원배열 edge를 받아서 1번 노드에서 가장 멀리 떨어진 노드의 개수를 반환하는 함수를 만들어야 한다.

 

문제 풀이

 BFS로 풀면 간단한 문제이다. edge를 이용해 노드의 연결을 확인하는 2차원 배열 map을 선언하고 채운다. 또한 각 노드까지의 거리를 저장할 distance 배열을 만든다.

 

 1부터 BFS로 탐색을 시작하는데 now와 연결되어 있으며, distance가 0인(아직 방문하지 않은) 노드들의 인덱스를 queue에 넣으면서 그 노드의 거리는 현재 노드의 거리 + 1로 초기화 한다.

 

 탐색이 종료되고 distance 배열이 채워졌으므로 IntStream을 이용해 배열에서 가장 큰 값과 동일한 값을 가진 인덱스의 개수를 반환한다.

 

나의 코드

import java.util.*;
import java.util.stream.IntStream;

public class 가장_먼_노드 {
    public int solution(int n, int[][] edge) {
        boolean[][] map = new boolean[n + 1][n + 1]; // 연결 확인 2차원 배열
        int[] distance = new int[n + 1]; //  각 노드의 거리 배열

        /* map 채우기 */
        for (int[] i : edge)
            map[i[0]][i[1]] = map[i[1]][i[0]] = true;

        /* bfs 탐색으로 시작점으로 부터 거리 계산 */
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);
        while (!queue.isEmpty()) {
            int now = queue.poll();
            for (int i = 2; i <= n; ++i) {
                if (map[now][i] && distance[i] == 0) {
                    queue.offer(i);
                    distance[i] = distance[now] + 1;
                }
            }
        }

        /* 최대 거리의 노드 수 반환 */
        return (int) IntStream.range(0, n + 1)
                .filter(i -> distance[i] == Arrays.stream(distance).max().getAsInt())
                .count();
    }
}