[ BOJ ] DFS/BFS - 특정 거리의 도시 찾기

문제링크

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

문제설명

도시 1~N과 M개의 단방향도로가 있을때 특정 도시 X에서 갈 수 있는 모든 도시 중 최단거리가 K인 모든 도시 번호 출력 (단, 모든 도로 거리는 1)

문제풀이

시도1

from collections import deque
import sys

input = sys.stdin.readline

n, m, k, x = map(int, input().split())
path = [[] for _ in range(n+1)]
visited = [[False] for _ in range(n+1)]
visited[x] = True
answer = []
distance = 0

for _ in range(m):
    start, end = map(int, input().split())
    path[start].append(end)
queue = deque()
queue.append((x, distance))

while(queue):
    v, d = queue.popleft()
    if d == k:
        answer.append(v)
    if d > k:
        continue
    distance += 1
    for city in path[v]:
        if visited[city] == [False]:
            queue.append((city, distance))
            visited[city] = True
            
if len(answer) == 0:
    print(-1)
else:
    answer.sort()
    for a in answer:
        print(a)

시간초과가 나다가 입출력 sys로 바뀌니까 틀렸다고 나온다. 왜지 , ,,

시도 2

from collections import deque
import sys

input = sys.stdin.readline

n, m, k, x = map(int, input().split())
path = [[] for _ in range(n+1)]
distance = [-1]*(n+1)
#출발도시~출발도시는 0
distance[x] = 0

for _ in range(m):
    start, end = map(int, input().split())
    path[start].append(end)

queue = deque([x])
while queue:
    v = queue.popleft()
    for city in path[v]:
        if distance[city] == -1:
            queue.append(city)
            distance[city] = distance[v]+1

#print(distance)
check = False
for i in range(len(distance)):
    if distance[i] == k:
        print(i)
        check = True
if check == False:
    print(-1)