[python] 백준 18352번: 특정 거리의 도시 찾기 (BFS, deque, sys.stdin.readline() 개념 정리)

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

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

 

1. 코드 구현

from collections import deque
import sys
# input() 사용시 시간초과 > sys.stdin.readline()으로 대체 
n,m,k,x= map(int, sys.stdin.readline().split())
destination = [[] for _ in range(n+1)]

#도로 정보 입력 받기
for _ in range(m):
    a,b = map(int, sys.stdin.readline().split())
    destination[a].append(b)

# 모든 도시 최단 거리 초기화
distance = [-1]*(n+1)
distance[x]=0
# contain [x] in deq : 원소 x가 데크(Deque)에 저장
deq=deque([x])
while deq:
    target = deq.popleft()
    for next_node in destination[target]:
        if distance[next_node] == -1:
            distance[next_node] = distance[target] + 1
            deq.append(next_node)

check = True
for i in range(1,n+1):
    if distance[i] == k:
        print(i)
        check = False
# 최단거리가 k인 도시가 존재하지 않을 경우 
if check:
    print(-1)

 

deque란?

보통 큐(queue)는 선입선출(FIFO) 방식으로 작동한다. 반면, 양방향 큐가 있는데 그것이 바로 데크(deque)다.

즉, 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있다.

데크는 양 끝 엘리먼트의 append와 pop이 압도적으로 빠르다.

컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거를 할 경우, 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요되는 데 반해, 데크(deque)는 O(1)로 접근 가능하다.

 

• deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.
• deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다.
• deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
• deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.

 

from collections import deque
deq = deque([0])
for i in range(1,5):
    deq.append(i)

while deq:
    print(deq.popleft())

 

deq.popleft()에 대한 실행 결과

 

 

 

sys.stdin.readline()

반복문으로 여러줄을 입력받을 때 input() 대신 sys.stdin.readline()을 사용하면 처리 속도가 매우 빨라진다.

 

ex map(int, input().split())  => map(int, sys.stdin.readline().split())

    input()  => sys.stdin.readline()