18352 특정 거리의 도시 찾기 (Python)

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

 

import sys
input = sys.stdin.readline

# bfs 한 뒤에 depth가 k인 도시들을 출력한다
# visited 필요 없을듯?
# 최솟값을 담는 배열을 하나 만들면 될듯

N, M, K, X = map(int, input().split())

# graph = {i: [] for i in range(1,N+1)}
graph = [[] for i in range(N+1)]

for _ in range(M):
    A, B = map(int, input().split())
    graph[A].append(B)

from collections import deque

def bfs(node, waiting):
    visited = [-1]*(N+1)
    waiting.append(node)
    visited[node] = 0
    depth = 0

    while len(waiting) != 0:
        qSize = len(waiting)
        depth += 1

        for _ in range(qSize):
            node = waiting.popleft()
            for near in graph[node]:
                # 최단거리 갱신 및 조건 파악
                if visited[near] == -1:
                    waiting.append(near)
                    visited[near] = 0

        if depth == K:
            return waiting
        
    return waiting

waiting = deque()

courses = list(bfs(X, waiting))
if len(courses) == 0:
    print(-1)
else:
    courses.sort()
    for course in courses:
        print(course)

 

여러 가지 바꾸면서 최적화했는데 아무리 해도 안됐었음.
알고보니 return을 depth == K일때만 반환하는 걸로 해놔서 그랬음.
무조건 depth == K인 상황이 발생할거라고 생각했는데 아니었나봄.
그래프가 쪼개져 있거나 하면 안될 것으로 생각됨.
return을 생략하는 것에 확신을 가지면 안되겠다는 교훈을 얻음.
기본은 지키라고 있는거구나.