[BOJ] 18352 특정 거리의 도시 찾기 - python

18352번: 특정 거리의 도시 찾기 (acmicpc.net)

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

 

시작 노드로부터 일정한 거리의 노드를 찾는 문제이다.

 

거리를 저장하는 부분에서 많은 시간이 걸렸다.

 

처음엔 방문 여부를 저장하는 visited와 거리를 저장하는 distance list를 따로 사용하였는데,

코드를 좀 더 간결하게 만들기 위해 visited_dis 하나로 통합하였다.

 

처음 제출에서는 리스트 형태의 큐를 사용하였더니 시간 초과가 발생했다.

deque를 사용하니 해결할 수 있었다.

import sys
from collections import deque

# N: 도시의 개수, M: 도로의 개수, K: 거리 정보, X: 출발 도시의 번호
N, M, K, X = map(int, sys.stdin.readline().split())

visited_dis = [-1] * (N+1)
graph = [[] for _ in range(N+1)]
queue = deque()

for _ in range(M):
    a,b = list(map(int, sys.stdin.readline().rstrip().split()))
    graph[a].append(b)

def bfs(n):
    queue.append(n)
    visited_dis[n] = 0

    while queue:
        node = queue.popleft()
        for i in graph[node]:
            if visited_dis[i] == -1:		# 현재 노드와 인접한 노드에 (현재 거리+1) 거리를 저장한다.
                visited_dis[i] = visited_dis[node] + 1
                queue.append(i)

bfs(X)

for i in range(1, N+1):
    if visited_dis[i] == K:
        print(i)

if K not in visited_dis:
    print(-1)