[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.