[BOJ][Python]18352 풀이

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

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

import heapq
import sys
ssr = sys.stdin.readline

INF = 300001

def dijkstra():
    while h:
        cur_dist, cur_node = heapq.heappop(h)
        if cur_dist > dist[cur_node]:
            continue
        for next_dist, next_node in routes[cur_node]:
            if dist[cur_node]+next_dist < dist[next_node]:
                dist[next_node] = dist[cur_node] + next_dist
                heapq.heappush(h, (dist[next_node], next_node))
        
n, m, k, x = map(int, ssr().split())
routes = [[] for _ in range(n+1)]
for _ in range(m):
    departure, arrival = map(int, ssr().split())
    routes[departure].append((1, arrival))
dist = [INF for _ in range(n+1)]
h = [(0, x)]
dist[x] = 0
dijkstra()
ans = []
for i in range(1, n+1):
    if dist[i] == k:
        ans.append(i)
if len(ans) != 0:
    print(*ans, end='\n')
else:
    print(-1)

 

모든 거리가 다 1로 주어지기 때문에 데이크스트라를 쓰지 않아도 풀 수 있습니다. 저는 그냥 연습하려고 데이크스트라로 풀어봤어요. 요 며칠 계속 유니온파인드만 풀어서 코드가 뚝딱 나오진 않고 조금 헤맸네요. 따로 거리가 주어지지 않아서 저장할 때 거리를 포함시켜서 저장했는데 생각해보면 굳이 그럴필요없이 배열을 갱신해야할 때 그냥 1만 더해주면 되겠어요.

 

데이크스트라 알고리즘에 대해 정리한 글을 업로드했습니다. 데이크스트라를 좀 더 알고 싶은 분들은 보시면 도움이 될 거라고 생각해요.

https://justduke.tistory.com/356

[Algorithm][Python]데이크스트라(Dijkstra) 최단 경로 알고리즘 + 코드