특정 거리의 도시 찾기

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

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

문제설명:

대표적인 다익스트라 문제, x으로 부터 거리가 k 인 지점을 찾아라

실버2

소요시간:

16분

 

1차 시도(정답):

#한곳에서 다른곳들 까지 최소거리 다익스트라
import sys
from collections import deque
input = sys.stdin.readline

n,m,k,x = map(int,input().split())
INF = int(1e9)

graph = [[] for _ in range(n+1)]
distance = [INF]*(n+1)

for _ in range(m):
	s,e = map(int,input().split())
	graph[s].append((e,1))

q = deque([])
q.append((x,0))
distance[x] = 0 

while q:
	go , dist = q.popleft()
	if dist>distance[go]:
		continue

	for i in graph[go]:
		cost = dist + i[1]
		if cost<distance[i[0]]:
			distance[i[0]] = cost
			q.append((i[0],cost))
piv =1
for i in range(1,n+1):
	if distance[i] == k:
		print(i)
		piv= 0

if piv:
	print(-1)

사실 매번 조금씩 헷갈리긴 한데, 그래도 풀어보면 곧 잘맞춘다. 

비슷한 유형의 어려운 문제들을 풀며 디테일을 확인하자