STUDYING/Algorithm

[Programmers] 가장 먼 노드

EOZIN 2021. 9. 27. 00:38
728x90

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

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int result = 0;
        
        ArrayList<Integer>[] list = new ArrayList[edge.length];
        
        for(int i = 0; i < n; i++) {
            list[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < edge.length; i++) {
            int num1 = edge[i][0] - 1;
            int num2 = edge[i][1] - 1;
            list[num1].add(num2);
            list[num2].add(num1);
        }
        
        Queue<int[]> q = new LinkedList<>();
        boolean[] visit = new boolean[n];
        
        q.add(new int[]{0, 0}); // num, count
        visit[0] = true;
        
        int count = 0;
        
        while (!q.isEmpty()) {
            int[] now = q.poll();
            
            for (int next : list[now[0]]) {
                if (visit[next]) continue;
                visit[next] = true;
                q.add(new int[]{next, now[1] + 1});
                
                if (now[1] + 1 > count) {
                    count = now[1] + 1;
                    result = 1;
                } else if (now[1] + 1 == count) {
                    result++;
                }
            }
        }
        
        return result;
    }
}