특정 거리의 도시 찾기

문제 Acmicpc

Solution

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
from collections import deque

n,m,k,x=map(int,input().split())
node=[[] for _ in range(n+1)]

for _ in range(m):
    a,b=map(int,input().split())
    node[a].append(b)

dist=[-1]*(n+1)
dist[x]=0

q=deque([x])

while q:
    now=q.popleft()
    for i in node[now]:
        if dist[i] == -1:
            dist[i]=dist[now]+1
            q.append(i)

for idx,d in enumerate(dist):
    if d == k:
        print(idx)
        break
else:
    print(-1)

모든 도로의 거리는 1에서 너비 우선 탐색을 사용하는게 쉽겠구나라고 생각할 수 있어야 한다.

너비 우선 탐색은 기본적으로 큐를 이용하므로 파이썬에서는 deque를 사용한다. 기본 스택으로 선언하고 pop(0)을 사용하면 분명히 시간초과가 난다.

1
2
3
4
5
6
7
8
9
10
11
dist=[-1]*(n+1)
dist[x]=0

q=deque([x])

while q:
    now=q.popleft()
    for i in node[now]:
        if dist[i] == -1:
            dist[i]=dist[now]+1
            q.append(i)

BFS를 구현한 부분이다. 방문했던 노드인지 확인하고 최단 거리를 저장하기 위해 dist 변수를 -1로 초기화하여 선언한다. 이후 덱에서 탐색할 노드를 popleft()하고, 노드의 각 경로를 dist를 검사하여 방문했던 노드인지 확인한 후, 미방문 노드이면 거리를 설정하고 다시 큐에 넣어준다.

BFS로 풀면 되겠다는 것을 바로 떠올리면 쉽게 풀 수 있지만, 아직 경로 관련 문제에서 이건 DFS, 저건 BFS라고 확신하기가 어렵다. 더 공부해야겠다.