[Programmers] - 가장 먼 노드 (BFS)

문제

BFS에 익숙해지고 싶은 문제이다….

코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        int max = 0;
        Queue<Integer> q = new LinkedList<Integer>();
        boolean[][] visited = new boolean[n+1][n+1];
        int[] distance = new int[n+1];
        
        for(int i=0;i<edge.length;i++){// 길 뚫기
            visited[edge[i][0]][edge[i][1]] = true;
            visited[edge[i][1]][edge[i][0]] = true;
        }
        
        q.offer(1);
        
        while(!q.isEmpty()){
            int value = q.poll();
            for(int i=2;i<=n;i++){//1은 안해도되니 2부터
                if(distance[i] == 0 && visited[value][i]){//길이 뚫려있고 거리0이면
                    distance[i] = distance[value] +1;// +1길이 이어주기
                    q.offer(i);//어차피 정렬 안해도 모두 for문으로 돌아본다.
                }
            }
        }
        
        for(int i=2;i<=n;i++){//최대값 구하기
            max = Math.max(max, distance[i]);
        }
        
        for(int i=2;i<=n;i++)//최대값과 같으면
            if(max == distance[i]) answer++;
        
        return answer;
    }
}

코드 설명

주석으로 모두 설명했다.

요약

• BFS에 자주 익숙해지자.