[프로그래머스] 가장 먼 노드 - JAVA [자바]

링크

관찰

최단 경로로 이동했을 때 가장 멀리 떨어진 노드가 몇 개인지를 return한다.

기초적인 BFS문제이다. 각 간선들의 길이를 고려하지 않아도 된다. 트리가 주어졌을 때, 같은 level의 노드의 개수가 몇개인지를 묻는 문제와 크게 다를게 없다.

주어진 정보에서 인접행렬 or 인접 리스트를 만들고, "1"에서 부터 BFS하면 된다.

코드

import java.util.*;

class Solution {

    boolean[] visited;
    int[] dist;
    List<Integer>[] adj;

    public int solution(int n, int[][] edge) {
        int answer = 0;
        adj = new List[n + 1];
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] line : edge) {
            int from = line[0];
            int to = line[1];
            adj[from].add(to);
            adj[to].add(from);
        }

        visited = new boolean[n + 1];
        dist = new int[n + 1];

        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        visited[1] = true;

        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int next : adj[cur]) {
                if (visited[next]) {
                    continue;
                }
                q.add(next);
                visited[next] = true;
                dist[next] = dist[cur] + 1;
            }
        }

        int max = 0;
        for (int i = 1; i <= n; i++) {
            max = Math.max(max, dist[i]);
        }

        for (int i = 1; i <= n; i++) {
            if (dist[i] == max) {
                answer++;
            }
        }

        return answer;
    }
}