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

[프로그래머스] 49189 가장 긴 증가하는 부분 수열 - JAVA

문제

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

 

문제 분석

조건

• 1번 노드에서 출발하여 가장 멀리 떨어진 노드가 몇 개인지 구하는 문제

풀이방법

• 인접리스트로 그래프를 구성하고 1번 노드부터 탐색한다.
• 방문한 노드마다 거리를 저장하고 카운트 한 뒤, 가장 먼 거리의 카운트를 출력한다.

코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        List<Integer>[] graph = new List[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int[] e : edge) {
            graph[e[0]].add(e[1]);
            graph[e[1]].add(e[0]);
        }

        int[] counts = new int[20005];
        boolean[] visited = new boolean[n + 1];
        Deque<Node> q = new ArrayDeque<>();
        q.add(new Node(1, 0));
        visited[1] = true;
        int weight = 0;
        while (!q.isEmpty()) {
            Node now = q.poll();
            weight = now.count;
            counts[weight]++;
            for (int next : graph[now.num]) {
                if (!visited[next]) {
                    visited[next] = true;
                    q.add(new Node(next, weight + 1));
                }
            }
        }
        return counts[weight];
    }
}

class Node {
    int num;
    int count;

    public Node(int num, int count) {
        this.num = num;
        this.count = count;
    }
}