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

문제

• 1 ~ N번의 도시에 M개의 단방향 도로가 존재한다.
  특정 도시 X번에서 출발해 도달할 수 있는 모든 도시 중 최단 거리가 정확히 K인 모든 도시의 번호 리턴하기
• 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력

 

• 2 <= N <= 300,000
• 1 <= M <= 1,000,000
• 1 <= K <= 300,000

 

풀이 1

• 플로드 와샬로 하면 시간 초과임.
• BFS 방법으로 K 깊이까지 보낸 뒤, 해당 최단거리의 도시 번호 모두 출력하기

 

시간 초과 -> pypy로 하면 통과 됨

from collections import deque

N, M, K, X = map(int, input().split())
roads = [[] for _ in range(N+1)]
for _ in range(M) :
    a, b = map(int, input().split())
    roads[a].append(b)

visited = [False] * (N+1)
visited[X] = True
q = deque([([X], 0)])

while q :
    cities, dist = q.popleft()

    if dist == K :
        if cities :
            for city in sorted(cities) :
                print(city)
        else :
            print("-1")
        break

    nxt_cities = []
    for city in cities :
        for nxt in roads[city] :
            if not visited[nxt] :
                nxt_cities.append(nxt)
                visited[nxt] = True
    q.append((nxt_cities, dist+1))

 

풀이 2

• 입력이 많은 문제이므로 다음 코드를 추가해준다.

 

import sys

input = sys.stdin.readline

 

 

 

References

• 백준 최단거리