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

문제 링크

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

풀이 과정

정점 1로부터 가장 멀리 있는 정점들의 개수를 구하는 문제입니다. bfs 를 사용하여 각 노드들을 방문했으며, 루트(정점 1)로부터 몇 번째로 방문했는지 그 개수를 리스트에 저장해 두었습니다.

2차원 배열로 간선 정보가 주어졌기 때문에, 행을 고정시킨 후 시작점을 0번 째 열, 1번 째 열 각각에서 비교했습니다.

큐의 기존 크기 만큼 poll 을 한다는 점이 문제의 핵심이었다고 생각합니다.

코드

import java.util.*;

public class Main {
    public static int solution(int n, int[][] edge) {
        int answer = 0;

        boolean[] visit = new boolean[n + 1];
        List<int[]> list = new ArrayList<>();

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

        int cnt = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();

            for (int s = 0; s < size; s++) {
                int now = queue.poll();

                for (int i = 0; i < edge.length; i++) {
                    if (edge[i][0] == now && !visit[edge[i][1]]) {
                        visit[edge[i][1]] = true;
                        queue.add(edge[i][1]);
                        list.add(new int[]{edge[i][1], cnt + 1});
                    } else if (edge[i][1] == now && !visit[edge[i][0]]) {
                        visit[edge[i][0]] = true;
                        queue.add(edge[i][0]);
                        list.add(new int[]{edge[i][0], cnt + 1});
                    }
                }
            }

            cnt++;
        }

        Collections.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[1] - o1[1];
            }
        });

        for (int[] arr : list) {
            if (arr[1] != list.get(0)[1]) break;
            answer++;
        }

        return answer;
    }

    public static void main(String[] args) {
        int n = 6;
        int[][] vertex = {{3, 6}, {4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2}};

        solution(n, vertex);
    }
}