문제
N개의 헛간과 M개의 양방향 통로가 있다. 1번 헛간에서 가장 먼 헛간의 번호, 거리, 같은 거리의 헛간 수를 구하라.
입력
헛간 수 N, 통로 수 M과 각 통로의 양 끝 헛간 번호가 주어진다.
출력
가장 먼 헛간 번호(여럿이면 가장 작은 번호), 거리, 같은 거리의 헛간 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
6 7 3 6 4 3 3 2 1 3 1 2 2 4 5 2 | 4 2 3 |
풀이
1번 헛간에서 BFS로 모든 헛간까지의 최단 거리를 구한다.
- 1번에서 BFS를 실행하여 각 헛간까지의 거리를 기록한다
- 최대 거리를 가진 헛간 중 가장 작은 번호를 찾는다
- 최대 거리와 같은 거리의 헛간 개수를 센다
핵심 아이디어: BFS는 가중치 없는 그래프에서 최단 거리를 보장하므로, 한 번의 BFS로 모든 거리를 구할 수 있다.
코드
from collections import deque
def bfs(node):
q = deque()
q.append(node)
check[node] = 1
while q:
node = q.popleft()
for n in graph[node]:
if check[n] == 0:
check[n] = check[node] + 1
q.append(n)
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
u, v = map(int, input().split())
graph[u].append(v)
graph[v].append(u)
check = [0] * (N + 1)
bfs(1)
m = max(check)
print(check.index(m), m - 1, check.count(m))복잡도
- 시간: O(V + E)
- 공간: O(V + E)