[탐색/다익스트라] 백준 18352 특정 거리의 도시 찾기 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

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

 

 

 

2. 문제 풀이

 X 도시로부터 최단거리가 K인 도시를 찾는 문제입니다.

 

2022.03.22 - [Algorithm] - [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로

[Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로

 한 곳으로부터의 최단거리를 구하는 문제이므로, '다익스트라 알고리즘'을 사용합니다. 다익스트라에 관한 설명과 코드는 위 글에서 보실 수 있습니다.

 

 

 

3. 코드

import heapq  # 우선순위 큐 구현을 위함
import sys
input = sys.stdin.readline

# 입력
N, M, K, X = map(int, input().split())  # node, edge, 최단거리, 시작점
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append((b, 1))  # 도착지, 가중치

 다익스트라 알고리즘은 자신과 가까운 도시부터 탐색합니다. 이를 효율적으로 구현하기 위해, 우선순위 큐를 사용합니다. 우선순위 큐는 최소값부터 반환하는 특성을 갖고 있어, 최소 힙 구조라고도 합니다.

 

 

# 다익스트라 최적경로 탐색
def dijkstra(graph, start):
    distances = [int(1e9)] * (N+1)  # 처음 초기값은 무한대
    distances[start] = 0  # 시작 노드까지의 거리는 0
    queue = []
    heapq.heappush(queue, [distances[start], start])  # 시작 노드부터 탐색 시작

    while queue:  # queue에 남아있는 노드가 없을 때까지 탐색
        dist, node = heapq.heappop(queue)  # 탐색할 노드, 거리

        # 기존 최단거리보다 멀다면 무시
        if distances[node] < dist:
            continue

        # 노드와 연결된 인접노드 탐색
        for next_node, next_dist in graph[node]:
            distance = dist + next_dist  # 인접노드까지의 거리
            if distance < distances[next_node]:  # 기존 거리 보다 짧으면 갱신
                distances[next_node] = distance
                heapq.heappush(queue, [distance, next_node])  # 다음 인접 거리를 계산 하기 위해 큐에 삽입
    return distances

 다익스트라 알고리즘을 구현합니다. 그리디 방식으로, 현재까지 탐색한 최단거리를 바탕으로 다른 노드의 최단거리를 계산합니다.

 A -> B -> C 로 가는 경로가 있다면, A에서 B로 갈 때도 최단경로를 이용하고 B에서 C로 갈 때도 최단 경로를 이용해야겠죠?

 

 

# 출력
dist_start = dijkstra(graph, X)
find = False
for idx, i in enumerate(dist_start):
    if i == K:
        print(idx)
        find = True
if not find:
    print(-1)

 다익스트라 알고리즘을 통해 계산한 최단거리 중 K인 도시를 셉니다. 만약 없다면 -1를 출력합니다.