가장 먼 노드

사용 알고리즘: bfs

사용 언어: java

 

import java.util.*;
import java.io.*;

class Solution {
    static int answer;
    static int farthestWay;
    static ArrayList<Integer>[] al;
    static boolean[] visited;
    
    public int solution(int n, int[][] edge) {
        al = new ArrayList[n+1];
        for(int i=0; i<n+1; i++) {
            al[i] = new ArrayList<Integer>();
        }
        for(int i=0; i<edge.length; i++) {
            int a = edge[i][0];
            int b = edge[i][1];
            al[a].add(b);
            al[b].add(a);
        }
        visited = new boolean[n+1];
        bfs(1);
        
        return answer;
    }
    
    private static void bfs(int v) {
        Queue<int[]> q = new ArrayDeque();
        q.add(new int[] {v, 0});
        visited[1] = true;
        
        while(!q.isEmpty()) {
            int[] p = q.poll();
            int vertex = p[0];
            int howfar = p[1];
            for(int nextNode : al[vertex]) {
                if(!visited[nextNode]) {
                    visited[nextNode] = true;
                    q.add(new int[] {nextNode, howfar+1});
                    if(howfar+1 > farthestWay) {
                        System.out.print(farthestWay+" -> ");
                        farthestWay = howfar+1;
                        answer=1; //아악!
                        System.out.println(farthestWay);
                    }
                    else if(howfar+1 == farthestWay) {
                        answer++;
                    }
                }
            }
        }
    }
}

 

n의 값은 최대 20000이니까 인접리스트 활용

같은 depth 개수 구하기니까 bfs 적용

가장 먼 거리를 새로 찾았을 때 answer을 1로 초기화하는 코드를 잊어버려서 틀림