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

문제

[가장 먼 노드]

풀이

• 주어진 배열을 인접리스트로 구성한다
• queue에서 노드를 꺼내고 w와 max값을 비교해서 업데이트
• bfs로 노드를 순회하면서 w를 증가시킴
• 중복 방문을 피하기 위해 visited로 검사
• 각 노드마다 1에서부터 떨어진 거리를 저장한 weightArr를 순회하면서 max값이 몇 개인지 센다

코드

import java.util.HashMap;
import java.util.Map;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class Solution {
    public int solution(int n, int[][] edge) {
        Map<Integer, List<Integer>> graph = new HashMap<>();

        for(int[] e : edge) {
            int from = e[0];
            int to = e[1];
            graph.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
            graph.computeIfAbsent(to, k -> new ArrayList<>()).add(from);
        }
        
        boolean[] visited = new boolean[n + 1];
        int[] weightArr = new int[n + 1];
        
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{1, 0});
        
        visited[1] = true;
        
        int max = 0;
        
        while(!queue.isEmpty()){
            int[] e = queue.poll();

            int node = e[0];
            int w = e[1];

            weightArr[node] = w;

            if(w > max) {
                max = w;
            }

            if(graph.containsKey(node)){
                for(int neighbor : graph.get(node)){
                    if(!visited[neighbor]){
                        visited[neighbor] = true;
                        queue.add(new int[]{neighbor, w+1});
                    }
                }
            }
        }
        
        int answer = 0;
        for(int w : weightArr){
            if(w == max) answer++;
        }
        
        return answer;
    }
}

정리

• 인접 리스트를 구성할 때 HashSet의 computeIfAbsent을 사용