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

코딩테스트 연습 - 가장 먼 노드 | 프로그래머스 (programmers.co.kr)

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

어떻게 생각하고 문제를 풀었는가?

Queue를 사용한 BFS를 통해 1번 노드로부터 각 노드로의 최단 경로를 찾을 수 있습니다.

모든 노드까지의 최단 경로를 찾은 후 각 거리의 길이를 계산함으로서 최대 값을 갖고 있는 원소의 수를 알아낼 수 있겠다고 생각하였습니다.

코드

import java.util.*;
class Solution {
    private boolean[][] lines;
    private int[] dists;
    public int solution(int n, int[][] edge) {
        lines = new boolean[n][n];
        dists = new int[n];
        for(int[] line : edge){
            lines[line[0]-1][line[1]-1] = true;
            lines[line[1]-1][line[0]-1] = true;
        }
        Queue<Integer> directions = new LinkedList<>();
        directions.offer(0);
        while(!directions.isEmpty()){
            int start = directions.poll();
            for(int i=1;i<n;i++){
                if(dists[i]==0 && lines[start][i]){
                    dists[i] = dists[start]+1;
                    directions.offer(i);
                }
            }
        }        
        int max=0, count=0;
        for(int dist : dists){
            if(max<dist){
                max=dist; 
                count=1;  
            } 
            else if(max==dist) count++;
        }
        
        return count;
    }
} 

설계를 바탕으로 코드를 작성하였습니다.

주어진 입력은 양방향의 연결을 하나의 배열로 표현한 것이므로 2차원 배열을 선언하여 각 노드에서 갈 수 있는 노드를 표현하였습니다.

또한 BFS에서 먼저 도착한 노드는 최단경로를 갖습니다. 따라서 boolean 배열을 선언하여 방문을 표현하기보다 최단 경로가 정의되어 있다면 Queue에 추가하지 않도록 코드를 작성하였습니다.