[PG] 가장 먼 노드 JAVA

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

코딩테스트 연습 - 가장 먼 노드

노드의 개수 int n, 각 노드의 연결 상태 int[][] edge 가 주어진다. (edge의 각 행 [a, b] 는 노드 a, b 사이가 연결되어있음을 뜻한다.)

 

시작 노드를 1번으로 하였을 때, 1번 노드에서 가장 멀리 떨어진 노드의 개수를 반환해야한다.

 

 

 

풀이 .

import java.util.*;

class Solution {

    ArrayList<Integer>[] list = null;
    boolean[] check = null;
    int[] dist = null;

    public void bfs(int start) {
        Queue<Integer> que = new LinkedList<>();
        que.add(start);
        check[start] = true;
        dist[start] = 1;

        while (!que.isEmpty()) {
            int now = que.poll();
            for (int i = 0; i < list[now].size(); i++) {
                int next = list[now].get(i);
                if (check[next] == false) {
                    que.add(next);
                    check[next] = true;
                    dist[next] = dist[now] + 1;
                }
            }
        }
    }

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

        // 0번 인덱스는 무시하고 1번부터 사용
        list = new ArrayList[n + 1];
        check = new boolean[n + 1];
        dist = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        for (int[] connect : edge) {
            int u = connect[0];
            int v = connect[1];
            list[u].add(v);
            list[v].add(u);
        }

        bfs(1);

        int max = 0;
        for(int d : dist) if(max < d) max = d;
        for(int d : dist) if(max == d) answer++;

        return answer;
    }
}

 

최단 거리, 최장 거리 문제는 웬만해선 BFS로 해결된다.

 

BFS 는 현재 노드에서 1만큼 떨어진 노드들을 우선적으로 탐색하기 때문에 시작 노드에서부터의 거리를 공평하게 잴 수 있다.