[JAVA/BFS] 가장 먼 노드

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

프로그래머스

 

 

 

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        
        // edge와 방문 기록 저장
        Map<Integer, List<Integer>> edgeMap = new HashMap<>();
        boolean[] visited = new boolean[n+1];
        
        // edgeMap 초기화
        for(int i=1; i<=n; i++) {
            edgeMap.put(i, new ArrayList<>());
        }
        
        // 빠른 계산을 위해 edge를 Map으로 만들기
        for(int[] e : edge) {
            // 양방향성
            edgeMap.get(e[0]).add(e[1]);
            edgeMap.get(e[1]).add(e[0]);
        }

        // BFS로 연산하면 단순함.
        // Integer[]는 점, 거리 순
        Queue<Integer[]> bfsQueue = new LinkedList<>();

        // 초기 세팅
        int max = 1;
        bfsQueue.add(new Integer[]{1, max});
        visited[1] = true;
        
        // 연산 시작
        while(!bfsQueue.isEmpty()) {
            Integer[] now = bfsQueue.poll();
            
            // max 갱신 및 answer 갱신
            if(max == now[1]) {
                // max와 같으면 answer을 더함
                answer++;
            }
            else {
                // max가 갱신되었으면 answer이 초기화됨.
                answer = 1;
            }
            max = Math.max(now[1], max);
            
            // 방문하지 않은 점 하나씩 추가
            for(int spot : edgeMap.get(now[0])) {
                if(!visited[spot]) {
                    bfsQueue.add(new Integer[]{spot, now[1]+1});
                    visited[spot] = true;
                }
            }
            
        }
        
        return answer;
    }
}