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라고 확신하기가 어렵다. 더 공부해야겠다.