백준 18352 - 특정 거리의 도시 찾기 (파이썬 python)

백준 18352 - 특정 거리의 도시 찾기 (파이썬 python)

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

풀이 및 접근 방법

• 최단 경로를 구하는 문제이므로 BFS 방법으로 풀이합니다. DFS BFS 비교
• deque 쓰지 않고 list와 list method로 풀었을 때 시간 초과였습니다. → queue, stack 관련 문제일 때 deque 사용
• 기존에 하던대로 내장함수 input()을 사용하니 입력 시간이 길어서 그런지 시간초과가 발생하였습니다. 
• → input = sys.stdin.readline 으로 데이터를 받아두고 그 뒤로 input().split() 을 사용. (꼭 변수명으로 input을 사용하지 않아도 괜찮습니다.)
• 방문 표시는 distance list를 만들어서 방문하지 않았으면 -1, 방문했으면 해당 node까지의 최소거리를 distance에 넣어 방문을 표시합니다.
• 노드가 1씩 올라가는 자연수로 표현되면 list와 그 idx로 방문 표시를 합니다. ( 단방향 인접 리스트로 만들기 위해 dictionary 자료형을 쓰면 과정이 복잡해져서 그런지 시간초과가 발생했습니다. )

Python 빠른 입력

rstrip을 하라는 건 문자열 자체를 변수에 저장하고 싶을 때 얘기지, 개행문자가 맨 끝에 들어와도 int 변환이나 split()을 그대로 할 수 있습니다. 즉 int(sys.stdin.readline()), sys.stdin.readline().split() 이렇게 해도 아무 문제 없습니다. 참고로 이름이 꽤 길기 때문에 저는 input = sys.stdin.readline을 맨 처음에 함으로써 쓰는 편입니다.

(출처 https://www.acmicpc.net/board/view/22716 )

Code

from collections import deque
import sys

input = sys.stdin.readline

n, m, k, x = map(int, input().split() )
graph = [ [] for _ in range(n+1) ] # n+1 개의 row 생성 idx 맞추기 위해서 n+1 개 생성

for _ in range(m):
    a,b = map(int,  input().split() )
    graph[a].append(b)
    
distance    = [-1] * (n+1)
distance[x] = 0    

q = deque([x])
while q:
    now = q.popleft()
    for next_node in graph[now]:
        if distance[next_node] == -1:
            distance[next_node] = distance[now] + 1
            q.append(next_node)
    
check = False
for i in range(1,n+1):
    if distance[i] == k:
        print(i)
        check = True
        
if check == False:
    print(-1)