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

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 30분 + a

1. 문제 설명

-  특정 거리가 주어지면, 각 노드들의 최단 거리 중에서 특정거리에 해당하는 노드들을 출력하는 문제

2. 접근 방식

- heapq 나 deque자료형을 이용해서 다익스트라 알고리즘을 구현하면 되는 문제였다.

- 처음에 deque로 구현했다가 시간초과가 계속 떠서, 후에 heapq로 구현했다. 그랬는데도 안돼서 검색해보니 sys.stdin.readline을 해야한다고 나와서 그렇게 해서 '시간초과'를 견뎌냈다.

3. 코드

import heapq
import sys

# 입력
input = sys.stdin.readline
n, m, k, start = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)

distance = [1e9] * (n+1)

# 풀이 함수
def solution(graph, start, distance, k):
    q = []
    heapq.heappush(q, start)
    distance[start] = 0
    
    while q:
        now = heapq.heappop(q)
        for i in graph[now]: # 2, 3 최단 경로 구해야지
            cost = distance[now] + 1
            if cost < distance[i]:
                distance[i] = cost
                heapq.heappush(q, i)
    result = []

    for v in range(len(distance)):
        if distance[v] == k:
            result.append(v)

    if (len(result) == 0):
        print(-1)
    else:
        result.sort()
        for r in result:
            print(r)
        
solution(graph, start, distance, k)

4. 코멘트

- 모니터 하나 새로 살 뻔 했다...

나는 또 처음에 고장난 줄 알았지...