[프로그래머스/Java] 가장 먼 노드

문제

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

---

문제 파악

• n개의 노드
• vertex 의 원소 [n, m] : 노드 n과 m이 이어져 있다는 뜻

---

접근 방법

1. 자기 자신의 값을 키로, 자신의 노드와 연결되어 있는 다른 노드들을 list로 하는 해시테이블 사용
2. 무방향 그래프 : n => m, m => n 둘 다 넣어주어야함
3. 초기값 1을 큐에 넣어주고 방문처리로 시작
4. 큐에서 노드를 꺼내어 현재 노드의 거리를 확인
5. 현재 노드의 거리가 최대 거리보다 크면 최대 거리를 업데이트한 후, 개수를 1로 설정
6. 현재 노드의 거리가 최대 거리와 같으면 count 증가
7. 현재 노드의 모든 인접 노드를 확인하여 아직 방문하지 않은 노드가 있으면 큐에 추가
8. 위를 반복 후 bfs가 끝나면 count 반환

---

코드 구현

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        
        for(int i = 1; i <= n; i++)
            graph.put(i, new ArrayList<>());
        
        for(int[] e : edge){
            graph.get(e[0]).add(e[1]);
            graph.get(e[1]).add(e[0]);
        }
        
        boolean[] visited = new boolean[n + 1];
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{1, 0});
        visited[1] = true;
        
        int maxDist = 0, cnt = 0;
        while(!q.isEmpty()){
            int[] cur = q.remove();
            
            if(maxDist < cur[1]){
                maxDist = cur[1];
                cnt = 1;
            }
            else if(maxDist == cur[1])
                cnt++;
            
            for(int next : graph.get(cur[0])){
                if(visited[next]) continue;
                else{
                    visited[next] = true;
                    q.add(new int[]{next, cur[1] + 1});
                }
            }
        }
        return cnt;
    }
}