[lv3] 가장 먼 노드

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

 

 

백만년만의 그래프탐색 풀이

노드에 비해 간선이 적어서 인접리스트로 구현했다.

어떤 노드에 도달하는 경우의 수는 구할 필요가 없으므로 bfs를 썼다.

iterator 문법이 가물해서 리마인드할 필요를 느꼈다.

 

import java.util.*;
import java.lang.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        int cnt = 0;
        
        int N = n;
        int eLen = edge.length;
        
        List<List> adj = new ArrayList<>();
        for(int i=0; i<=N; i++) {
            adj.add(new ArrayList<>());
        }

        for(int i=0; i<eLen; i++) {
            adj.get(edge[i][0]).add(edge[i][1]);
            adj.get(edge[i][1]).add(edge[i][0]);
        }
        
        Queue<int[]> q = new ArrayDeque<>();
        boolean[] visited = new boolean[N+1];
        
        q.offer(new int[]{1, 0});
        visited[1] = true;
        
        while(!q.isEmpty()) {
            int[] info = q.poll();
            int node = info[0];
            int depth = info[1];
            
            if(depth > answer) {
                answer = depth;
                cnt = 1;
            }
            else if(depth == answer) {
                cnt++;
            }
            
            Iterator<Integer> it = adj.get(node).iterator();
            for(int i=1; i<=adj.get(node).size(); i++) {
                int next = it.next();
                if(!visited[next]) {
                    q.offer(new int[]{next, depth+1});
                    visited[next] = true;
                }
            }
        }
        
        return cnt;
    }
}