가장 먼 노드

문제

풀이

import java.util.*;

class Solution {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int answer=0;
    static boolean[] ch;
    static int[] dis;
    static int max = Integer.MIN_VALUE;
    
    public static void BFS(int v){
        ch[v]=true;
        dis[v]=0;
        
        Queue<Integer> Q = new LinkedList<>();
        Q.offer(v);
        while(!Q.isEmpty()){
            int x = Q.poll();
            for(int nx : graph.get(x)){
                if(!ch[nx]){
                    ch[nx]=true;
                    Q.offer(nx);
                    dis[nx]=dis[x]+1;
                    if(dis[nx]>max) max=dis[nx];
                }
            }
        }
    }
    
    
    public int solution(int n, int[][] edge) {
        
        for(int i=0; i<=n; i++) graph.add(new ArrayList<>());
        
        for(int[] x : edge){
            int v = x[0];
            int w = x[1];
            graph.get(v).add(w);
            graph.get(w).add(v);
        }
        
        ch = new boolean[n+1];
        dis = new int[n+1];
        BFS(1);
        
        for(int num : dis){
            if(num == max) answer++;
        }
        return answer;
    }
}

일단 이런 그래프 문제에서 거리를 구하는 핵심.

1. 무조건 BFS가 좋다.
2. ArrayList<ArrayList<타입>> arr = new ArrayList<>(); 이런식으로 선언해서 노드 수만큼 담아야한다. 여기에다가 연결된 간선을 담는다.
3. 방향 그래프 , 무방향 그래프에 따라서 담아줘야함.
4. boolean ch[]를 만들어야 한다면 만들어준다.
5. 거리를 담을 dis[] 배열도 만들어준다.

위 조건을 지키면서 Q로 while()문을 오지게 돌려주면 쉽게 푼다.