|
import sys
input = sys.stdin.readline
Vn, En, k, x = map(int, input().split())
V = {}
for i in range(1, Vn + 1) :
V[i] = []
for i in range(En) :
v1, v2 = map(int, input().split())
V[v1].append(v2)
gone = [False for i in range(Vn+1)]
ans = []
def BFS(now) :
que = [[now, 0]]
while que :
q, d = que[0][0], que[0][1]
del que[0]
if d == k :
ans.append(q)
else :
for i in V[q] :
if not gone[i] :
gone[i] =True
que.append([i, d + 1])
gone[x] = True
BFS(x)
if ans == [] :
print(-1)
else :
ans.sort()
for i in ans :
print(i)
|
입력받은 E의 정보로부터 v간의 연결 정보를 기록한다.
연결된 점으로 확산되는 BFS를 정의한다. 거리가 k가 될 때 확산을 멈추고 ans에 저장된다.
'최소' 거리가 k인 점만을 요구하므로 중복 방문을 막기 위해 각 점의 방문 기록을 gone에 남긴다.
시작점 x에서 BFS를 실행 한 뒤 ans가 비었다면 -1을 출력하고 비지 않았다면 답을 출력한다.
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 2665 미로 만들기 (0) | 2021.11.20 |
|---|---|
| 파이썬 백준 1916 최소비용 구하기 (0) | 2021.11.20 |
| 파이썬 백준 2718 미로 탐색 (0) | 2021.11.20 |
| 파이썬 백준 2606 바이러스 (0) | 2021.11.20 |
| 파이썬 백준 11724 연결 요소의 개수 (0) | 2021.11.20 |