프로그래머스 가장 먼 노드 (JAVA)

코딩테스트 연습 > 그래프

---

가장 먼 노드

---

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

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

 

다익스트라 알고리즘을 사용하여 풀었다.

특이점은, cost가 없이 일정한 그래프이므로 boolean 2차원 배열로 그래프를 그렸다는 점이다.

 

import java.util.*;

class Solution {
    
    public int solution(int N, int[][] edge) {
        List<Integer> paths[] = new ArrayList[N+1];
        boolean[] visit = new boolean[N+1];
        boolean[][] path = new boolean[N+1][N+1];
        for(int i = 0; i<=N; i++){
            paths[i] = new ArrayList<>();
        }
        
        for(int[] e : edge){
            path[e[0]][e[1]] = true;
            path[e[1]][e[0]] = true;
        }
        Queue<Integer> que = new ArrayDeque<>();
        que.add(1);
        visit[1] = true;
        int qSize = que.size();
        while(!que.isEmpty()){
            qSize = que.size();
            for(int i = 0; i<qSize; i++){
                int now = que.poll();
                for(int j = 1; j<=N; j++){
                    if(!visit[j] && path[now][j]){
                        visit[j] = true;
                        que.add(j);
                    }
                }
            }    
            System.out.println(qSize);
        }
       return qSize;
    }
    
}