[백준/Python] 17204 죽음의 게임

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

알고리즘

그래프를 그리고, 0번에서 시작하여 k번까지의 최소 거리를 찾는 문제이다.

간선 사이의 거리를 1로 설정하여 다익스트라 알고리즘을 돌려준 뒤에 distance배열에서 k번째 원소의 값을 읽어와 INF면 -1을, 아니면 거리를 출력해주면 된다.

코드

import sys
import heapq

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

n, target = map(int, input().split())
graph = [[] for _ in range(n)]
distance = [INF] * n  

for a in range(n):
    b = int(input())
    graph[a].append((b, 1))  

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))  
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for next_node, cost in graph[now]:  
            new_cost = dist + cost
            if new_cost < distance[next_node]:  
                distance[next_node] = new_cost
                heapq.heappush(q, (new_cost, next_node))

dijkstra(0)

print(-1 if distance[target] == INF else distance[target])