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

• 문제 - 가장 먼 노드

풀이과정

• BFS 방식으로 풀이를 진행

1. 사전준비
   • 각 Node마다 연결되어있는 Node들을 표현하기 위한 2차원 배열을 만든다. (boolean[n][n])
     • 이후 주어진 edge 정보를 바탕으로 서로 연결되어 있는 Node들 끼리는 해당 위치의 원소값을 true로 변경한다.
   • 1번 Node로부터 얼마만큼의 거리에 떨어져 있는지를 표현할 1차원 배열을 만든다. (int[n])
     • 여기서 원하는 결과는 가장 먼 거리에 있는 Node의 갯수이므로 정확한 최대 거리를 꼭 알아야 할 필요성은 없다.
     • 1번 Node로 부터 떨어져 있는 거리를 모르는 Node의 경우 원소값이 0인 상태로 존재한다.
2. 1번 Node 부터 BFS 탐색을 시작할 수 있도록 준비한다.
   • queue에 1번 Node를 enqueue 한다.
   • 위에서 만들어 둔 1차원 거리 배열의 1번 Node에 대한 원소값을 변경한다.
3. BFS 탐색 시작
   • queue가 완전히 empty 될 때 까지 아래 과정을 반복한다.
   • queue에서 Node 하나를 선택
   • 해당 Node에 연결되어있는 Node 배열을 순회하며 현재 Node와 연결되어 있으며 1번에서 준비한 거리 배열의 값이 아직 0으로 남아있는 Node를 찾아 queue에 추가하고, 해당 Node까지의 거리를 업데이트 한다.(현재 Node까지의 거리 + 1)
4. BFS 탐색이 종료되면 1번 과정에서 준비한 거리 배열에서 최대 거리를 찾고, 그 갯수를 세어 결과를 반환한다.

Code

import java.util.*;

class Solution {
    public int solution(int n, int[][] edges) {
        Queue<Integer> queue = new ArrayDeque<>();
        boolean[][] connected = new boolean[n][n];
        int[] distances = new int[n];

        // 세로축을 각 노드, 가로축을 연결된 노드로 가정. 연결 정보 업데이트
        for (int[] edge : edges) {
            connected[edge[0] - 1][edge[1] - 1] = true;
            connected[edge[1] - 1][edge[0] - 1] = true;
        }

        // 스타팅 지점 준비
        queue.offer(0); // 1번 노드
        distances[0] = 1; // dummy value

        // 탐색
        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int j = 0; j < size; j++) {
                int currentNode = queue.poll();

                for (int i = 0; i < connected[currentNode].length; i++) {
                    if (connected[currentNode][i] && distances[i] == 0) {
                        queue.offer(i);
                        distances[i] = distances[currentNode] + 1;
                    }
                }
            }
        }

        int farthest = Arrays.stream(distances).max().getAsInt();
        return (int) Arrays.stream(distances).filter(distance -> distance == farthest).count();
    }
}

결과