Post

[Programmers] #49189 - 가장 먼 노드 [Java][C++][Python]

[Programmers] #49189 - 가장 먼 노드 [Java][C++][Python]

문제 링크


1. 아이디어

1번 노드에서 최단경로의 간선 수가 가장 많은 노드가 몇 개인지 세는 문제로, 간선에 가중치가 없으므로 1번 노드에서 BFS를 하면 노드가 처음 닿는 레벨이 곧 최단경로의 간선 수이고, 가장 먼 노드는 마지막 레벨의 노드들이므로 마지막 레벨의 크기가 답이다. 노드가 최대 20,000개라 인접 행렬은 칸이 4억 개나 되어 인접 리스트로 그래프를 표현한다.


2. 코드

풀이 [Java][C++][Python]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        List<Integer>[] adj = new ArrayList[1 + n];
        for (int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] e : edge) {
            adj[e[0]].add(e[1]);
            adj[e[1]].add(e[0]);
        }

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

        boolean[] vis = new boolean[1 + n];
        vis[1] = true;

        int ans = 0;
        while (!q.isEmpty()) {
            ans = q.size();
            int sz = q.size();
            while (sz-- > 0) {
                int cur = q.poll();
                for (int nxt : adj[cur]) {
                    if (vis[nxt]) continue;
                    q.offer(nxt);
                    vis[nxt] = true;
                }
            }
        }

        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1 + 20000;
vector<int> adj[MAX_N];
bool vis[MAX_N];

int solution(int n, vector<vector<int>> edge) {
    for (auto& e : edge) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }

    queue<int> q;
    q.push(1);

    vis[1] = true;

    int ans = 0;
    while (!q.empty()) {
        ans = q.size();
        int sz = q.size();
        while (sz--) {
            int cur = q.front();
            q.pop();

            for (int nxt : adj[cur]) {
                if (vis[nxt]) continue;
                q.push(nxt);
                vis[nxt] = true;
            }
        }
    }

    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from collections import deque


def solution(n, edge):
    adj = [[] for _ in range(1 + n)]
    for u, v in edge:
        adj[u].append(v)
        adj[v].append(u)

    q = deque([1])

    vis = [False] * (1 + n)
    vis[1] = True

    ans = 0
    while q:
        ans = len(q)
        for _ in range(len(q)):
            cur = q.popleft()
            for nxt in adj[cur]:
                if vis[nxt]:
                    continue
                q.append(nxt)
                vis[nxt] = True

    return ans

This post is licensed under CC BY 4.0 by the author.