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

🔗 문제링크

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

👩🏻‍💻 코드 (dfs - 시간초과)

import java.util.*;

class Solution {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean[] visited;
    static int[] distance;
    
    public int solution(int n, int[][] edge) {
        visited = new boolean[n + 1];
        distance = new int[n + 1];
        int answer = 0;

        for (int i = 0; i <= n; i++) {
            graph.add(i, new ArrayList<>());
            distance[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < edge.length; i++) {     // 양방향 추가해주기
            graph.get(edge[i][0]).add(edge[i][1]);
            graph.get(edge[i][1]).add(edge[i][0]);
        }
        dfs(1, 0);

        int max = 0;
        for (int i = 2; i <= n; i++) {      // 가장 멀리 떨어진 거리
            max = Math.max(max, distance[i]);
        }

        for (int i = 2; i <= n; i++) {      // 가장 멀리 떨어진 노드 개수
            if (distance[i] == max) {
                answer++;
            }
        }

        return answer;
    }
    
    public static void dfs(int start, int cnt) {
        distance[start] = Math.min(distance[start], cnt);

        for (int adj : graph.get(start)) {
            if (!visited[adj]) {
                visited[adj] = true;
                dfs(adj, cnt + 1);
                visited[adj] = false;
            }
        }
    }
}

👩🏻‍💻 코드 (bfs - 통과)

import java.util.*;

class Solution {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean[] visited;
    
    public int solution(int n, int[][] edge) {
        visited = new boolean[n + 1];
        int answer;

        for (int i = 0; i <= n; i++) {
            graph.add(i, new ArrayList<>());
        }

        for (int i = 0; i < edge.length; i++) {     // 양방향 추가해주기
            graph.get(edge[i][0]).add(edge[i][1]);
            graph.get(edge[i][1]).add(edge[i][0]);
        }
        answer = bfs();
        return answer;
    }
    
    public static int bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        visited[1] = true;

        int cnt = 0;
        while (true) {
            Queue<Integer> temp = new LinkedList<>();

            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int adj : graph.get(cur)) {
                    if (!visited[adj]) {
                        temp.add(adj);
                        visited[adj] = true;
                    }
                }
            }

            if (temp.isEmpty()) break;
            queue.addAll(temp);
            cnt = temp.size();
        }

        return cnt;
    }
}

📝 정리

처음에 dfs로 풀었는데 시간 초과가 나버렸다. 아무래도 모든 경우의 수를 다 훑기 때문인 듯하다.

bfs 방법은 인접한 노드들을 queue에 추가해 주는 것인데, 바로 queue에 추가해 주지 않고 temp에 추가했다가 한 번에 queue에 추가하기 때문에 같은 거리에 있는 것들의 개수를 셀 수 있었다. => temp.size()
더 이상 인접한 노드가 없을 때까지 while 문이 반복되기 때문에 마지막으로 설정된 cnt = temp.size()가 가장 먼 노드의 개수를 나타낸다.

앞으로 dfs와 bfs 중에서 뭘로 풀지 잘 고려하여 선택해야겠다.