[프로그래머스/Graph] Level 3 가장 먼 노드 (JAVA)

문제

이번 토요일에 있을 네이버 코테 준비를 위해... 프로그래머스 환경에서 IDE와 구글링 없이 문제를 풀어보았다. 결과는... 효율 똥망...^^.. 클났다...ㅎㅎ..ㅎ....

---

풀이

문제 자체는 어렵지 않았다. IDE 없이 하나하나 다 치려니 멘붕이 와서 오래 걸렸을 뿐...

BFS로 접근했고, Stack이 아닌 Queue를 사용했다. 그래야 상위 노드부터 하위 노드까지 차례로 빠뜨리지 않고 접근이 가능하다.

또한 distance를 저장하기 위해 Node 클래스를 정의해서 활용했다.

코드

import java.util.*;

class Solution {
    
    private List<List<Integer>> graph;
    
    public int solution(int n, int[][] edges) {
        initGraph(n, edges);
        int[] distances = countDistances(n);
        return countFarthestNodes(distances);
    }
    
    private void initGraph(int n, int[][] edges){
        graph = new ArrayList<>();
        for (int i=0 ; i<n+1 ; i++)
            graph.add(new ArrayList<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
    }
    
    private int[] countDistances(int n){
        int[] distances = new int[n+1];
        Arrays.fill(distances, Integer.MAX_VALUE);
        
        boolean[] visited = new boolean[n+1];
        visited[1] = true;
        
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(1, 0));
        while(!queue.isEmpty()){
            Node current = queue.poll();
            for (int adjacent : graph.get(current.index)){
                if (!visited[adjacent]){
                    visited[adjacent] = true;
                    queue.offer(new Node(adjacent, current.distance + 1));
                    distances[adjacent] = Math.min(distances[adjacent], current.distance + 1);
                }
            }
        }
        return distances;
    }
    
    private int countFarthestNodes(int[] distances) {
        int max = findMaxValue(distances);
        int result = 0;
        for (int distance : distances)
            if (distance == max) result++;
        return result;
    }
    
    private int findMaxValue(int[] arr) {
        int result = Integer.MIN_VALUE;
        for (int i=2 ; i<arr.length ; i++)
            if (arr[i] != Integer.MAX_VALUE)
                result = Math.max(result, arr[i]);
        return result;
    }
}

class Node {
    
    int index;
    int distance;
    
    public Node(int index, int distance){
        this.index = index;
        this.distance = distance;
    }
}

그나마 요즘 자주 봐서 익숙한 유형이라 풀 수 있었던 것 같다. 내일 완전 새롭고 복잡한 문제를 맞닥뜨리면 얼마나 오래 걸릴지 걱정이 된다...ㅠㅠ