[Python] 백준 18352 특정 거리의 도시 찾기 | 다익스트라 알고리즘

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

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

 

 

문제 해결 포인트

- 다익스트라(Dijkstra) 알고리즘

 

- distance : X로부터 각 노드의 가장 짧은 경로. 경로가 없다면 무한수(INF)

- graph : 각 노드가 연결되어 있는 정보 (연결 리스트)

- q : 지금까지 계산 된 거리 중 간선이 가장 짧은 것을 구하기 위한 우선순위 큐(Priority Queue)

 

상세한 설명은 주석을 참고 바랍니다 

 

 

 

작성 코드

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

N, M, K, X = map(int, input().split())  # 노드수, 간선수, 목표 거리, 시작 노드
graph = [[] for _ in range(N+1)]  # 연결 리스트
distance = [INF]*(N+1)  # X로부터 각 노드 최소 거리, 무한수로 초기화

# 각 간선 연결
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)

def dijkstra(start):
    q = []
    distance[start] = 0  # start 노드 거리 초기화
    heapq.heappush(q, (0, start))  # 우선순위 큐에 (거리, 시작 노드) 삽입

    while q:  # 큐에 값이 있을 동안
        dist, now = heapq.heappop(q)  # 우선순위 큐에 존재하는 거리가 가장 짧은 노드
        if distance[now] < dist:  # 방문한 노드
            continue
        for i in graph[now]:  # now노드와 연결된 모든 노드
            cost = 1 + dist  # 1 + now노드의 최소 거리
            if cost < distance[i]:  # now -> i 거리가 작다면
                distance[i] = cost  # 업데이트
                heapq.heappush(q, (cost, i))  # 우선순위 큐 삽입


dijkstra(X)  # 실행 후 X로부터 각 노드가 떨어진 최소 거리 distance 작성 완료

flag = False  # K와 일치하는 거리가 있는지 판단
for i in range(1, N+1):
    if distance[i] == K:
        flag = True  # 일치 하는 것 존재
        print(i)
if not flag:  # 일치하는 것 존재하지 않음
    print(-1)

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚