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

• 파이썬으로 알고리즘을 풀 때, input을 입력받는 과정에서 input()을 사용하면 시간 초과가 나올 수 있음!
• sys.stdin.readline 을 사용하여 입력값을 받자
• 거리 정보를 받을 때 아래와 같이 리스트의 형식으로 저장하면 특정 노드로부터 시작하는 거리가 있는지 파악하기 수월하다!
• queue를 사용하여 탐색할 노드를 파악한다

for _ in range(M):
  a, b = map(int, input().split())
  dist[a].append(b)

 

✅ 문제 풀이 코드

import sys
from collections import deque
input = sys.stdin.readline

N, M, K, X = map(int, input().split())
dist = [[] for _ in range(N+1)]
cost = [-1] * (N+1)

# 거리 정보 입력받기
for _ in range(M):
  a, b = map(int, input().split())
  dist[a].append(b)

def searchDist(start):
  q = deque()
  q.append(start)
  cost[start] = 0 # 시작하는 노드 거리 초기화

  while q:
    tmp = q.popleft()
  
    for next in dist[tmp]:
      # tmp로부터 출발하는 도로가 있는지 찾는다
      if cost[next] == -1:  # 방문한적 없는 도시이면
        cost[next] = cost[tmp] + 1 # 현재 도시에서의 cost에 + 1 해주기
        q.append(next)

searchDist(X)

# 정답 출력하기
flag = True
for i in range(1, N+1):
  if cost[i] == K:  
    print(i)
    flag = False

if flag : print(-1)