정답 비율: 28.537%
문제 풀이
모든 간선의 비용이 동일할 때 최단 거리를 찾아야 한다면 bfs로 풀어보라고 한다. 모든 도시까지의 최단 거리를 계산한 뒤에, 각 최단 거리가 K인 경우를 찾으면 된다.
소스코드
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
37
38
39
40
41
42
43
import sys
from collections import deque
input = sys.stdin.readline
# 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X 입력받기
n, m, k, x = map(int, input().split())
# 인접 리스트 생성
graph = [[] for _ in range(n+1)] # 인덱스 0 버리고 1부터 시작
# 두 도시를 연결하는 도로 입력받기
for _ in range(m):
a, b = map(int, input().split())
graph[a].append(b)
# 출발 도시에서부터의 최단 거리 초기화
distance = [-1] * (n+1)
def bfs(graph, start, distance):
queue = deque([start])
distance[x] = 0 # 출발 도시까지의 거리는 0
while queue:
now = queue.popleft()
# 현재 도시에서 방문할 수 있는 모든 도시를 확인
for next in graph[now]:
# 아직 방문하지 않았다면
if distance[next] == -1:
queue.append(next)
# 최단 거리 갱신
distance[next] = distance[now] + 1
bfs(graph, x, distance)
# 최단 거리가 K인 도시 출력
check = False
for i in range(1, n+1):
if distance[i]==k:
print(i)
check = True
# K인 도시가 없으면 -1 출력
if check==False:
print(-1)