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

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

 

 

 

---

 

 

 

 

• 풀이

 

노드1이랑 연결되어있는 노드들은 첫번째로 먼 노드들입니다.

첫번째 노드랑 연결되어 있는 (지나쳐오지 않은)노드들은 노드1이랑 두번째로 멀리 연결되어 있는 노드들입니다.

......쭉 마지막으로 연결되어 있는 노드까지 가서 개수를 구해주었습니다.

 

 

• 코드

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        boolean[][] node = new boolean[n+1][n+1];
        boolean[] check = new boolean[n+1];
        for(int i = 0 ; i < edge.length; i++){
            node[edge[i][0]][edge[i][1]] = true;
            node[edge[i][1]][edge[i][0]] = true;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        int answer = 0;
        queue.add(1);
        
        while(!queue.isEmpty()) {
            answer = queue.size();
            
            for(int i = 0; i < answer; i++) {
                int pre = queue.poll();
                
                for(int next = 2; next <= n; next++){
                    if(check[next] || !node[pre][next]) continue;
                    check[next] = true;
                    queue.add(next);
                }
            }
        }
        
        return answer;
    }
}