[프로그래머스 알고리즘 고득점 Kit][그래프][Java] 가장 먼 노드

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

프로그래머스

정답 코드

문제를 대충 읽어서 최단 거리로 이동했을 때 
가장 먼 노드들의 개수를 구하는 건데
가장 먼 노드의 거리를 구했었다가 틀리고 바로 수정

 

bfs로 1번 노드에서 각 노드에 도달하기까지 지나온 최소 개수를 count배열로 저장하고
가장 많이 지나온(가장 먼) 노드를 찾기 위해 max 로 최대를 계속 업데이트해주고
마지막에 count 배열에 max와 같은 가장 멀리 떨어져 있는 노드들의 개수를 세고 반환해 준다.

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        ArrayList<Integer>[] graph = new ArrayList[n+1];
        for(int i=1; i<=n; i++) {
            graph[i] = new ArrayList<>();
        }
        for(int i=0; i<edge.length; i++){
            int u = edge[i][0];
            int v = edge[i][1];
            graph[u].add(v);
            graph[v].add(u);
        }
        Queue<int[]> q = new ArrayDeque<>();
        boolean[] visited = new boolean[n+1];
        int[] count = new int[n+1];
        count[1] = 1;
        q.add(new int[] {1, 1});
        int max = 0;
        visited[1] = true;
        while(!q.isEmpty()) {
            int[] curr = q.poll();
            int currX = curr[0];
            int currD = curr[1];
            for(int next : graph[currX]) {
                if(visited[next]) continue;
                
                int dist = currD + 1;
                count[next] = dist;
                max = Math.max(dist, max);
                q.add(new int[] {next, dist});
                visited[next] = true;
            }
        }
        int answer = 0;
        for(int i=1; i<=n; i++){
            if(count[i] == max) answer++;
        }
        return answer;
    }
}