[python] 백준 18352 특정 거리의 도시 찾기

https://www.acmicpc.net/problem/18352

18352번: 특정 거리의 도시 찾기

 

문제 해결

• 특정 지점까지 가는데 최소 거리가 k인 점을 찾는 문제 (DFS,BFS 다 되지만 거리가 정해져있으므로 BFS로 너비로 찾는 것이 좋다!)
• 양방향 도로가 아니라는 것에 주의하자!

 

CODE

import sys
from collections import deque
input = sys.stdin.readline

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


ans = []
visited = [-1 for _ in range(n+1)]

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


def bfs(v):
    queue = deque()
    queue.append(v)
    visited[v] += 1
    while queue:
        now = queue.popleft()
        for next in graph[now]:
            if visited[next] == -1:
                visited[next] = visited[now] + 1
                queue.append(next)
bfs(x)
for i in range(n+1):
    if visited[i] == k:
        print(i)
        ans.append(i)
if len(ans)==0:
    print(-1)