[프로그래머스/Java] Lv.3 - 가장 먼 노드

프로그래머스 Lv.3 - 가장 먼 노드

요구사항

• 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 문제
• 거리는 간선의 개수로 측정

접근 방식

BFS 로 1번 노드에서 출발해 각 노드까지의 거리를 측정했다.

핵심 아이디어

• BFS는 가까운 노드부터 탐색하므로 가장 마지막에 방문하는 노드들이 가장 먼 노드
• maxDist를 갱신할 때마다 cnt를 0으로 초기화
• 현재 dist가 maxDist와 같으면 cnt 증가

코드

import java.util.*;

class Node {
    int ver, dist;
    public Node(int ver, int dist) {
        this.ver = ver;
        this.dist = dist;
    }
}

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

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

        return bfs(n, graph);
    }

    public int bfs(int n, ArrayList<ArrayList<Integer>> graph) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(1, 0));

        boolean[] visit = new boolean[n+1];
        visit[1] = true;
        int maxDist = 0, cnt = 0;

        while (!q.isEmpty()) {
            Node node = q.poll();
            for (int next : graph.get(node.ver)) {
                if (visit[next]) continue;
                visit[next] = true;
                int dist = node.dist + 1;
                q.offer(new Node(next, dist));

                if (maxDist < dist) {
                    maxDist = dist;
                    cnt = 0;
                }
                if (maxDist == dist) cnt++;
            }
        }
        return cnt;
    }
}

다른 풀이 - dist 배열 활용

int[] dist = new int[n+1];
Arrays.fill(dist, -1);
dist[1] = 0;

Queue<Integer> q = new LinkedList<>();
q.offer(1);

while (!q.isEmpty()) {
    int cur = q.poll();
    for (int next : graph.get(cur)) {
        if (dist[next] != -1) continue;
        dist[next] = dist[cur] + 1;
        q.offer(next);
    }
}

int maxDist = Arrays.stream(dist).max().getAsInt();
return (int) Arrays.stream(dist).filter(x -> x == maxDist).count();

Node 클래스 없이 dist 배열로 관리하면 더 간결하다.

느낀점

• BFS는 가까운 노드부터 탐색하는 특성상 거리 측정 문제에 적합하다.
• maxDist 갱신 시 cnt를 초기화하는 아이디어로 깔끔하게 구현했다.
• dist 배열로 관리하면 Node 클래스 없이도 구현 가능하다.
• 자주 쓰는 Stream 패턴은 정리해두면 코테에서 유용하게 쓸 수 있다.

자주 쓰는 Stream 패턴 정리

// 최댓값
Arrays.stream(arr).max().getAsInt();

// 최솟값
Arrays.stream(arr).min().getAsInt();

// 합계
Arrays.stream(arr).sum();

// 조건에 맞는 개수
Arrays.stream(arr).filter(x -> x == target).count();

// 조건에 맞는 것만 배열로
Arrays.stream(arr).filter(x -> x > 0).toArray();