백준 18352번

접근 방식 (알고리즘 분류)

• 다익스트라 (단방향)

내풀이

import heapq, sys

input = sys.stdin.readline
INF = sys.maxsize

n, m, k, start = map(int, input().split())
graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)

for i in range(m):
    #a번에서 b번 노드로 가는 비용 c 저장
    a, b = map(int, input().split())
    graph[a].append((1,b))

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 i in graph[now]:
            #지금까지 온거리 + 지금 이동할 거리
            cost = dist + i[0]
            #위에서 계산한 거리가 현재 최저로 기록된 값보다 작다면 이때 최저로 갱신
            if cost < distance[i[1]]:
                distance[i[1]] = cost
                heapq.heappush(q, (cost, i[1]))

dijkstra(start)
if k not in distance:
    print(-1)
else:
    for i,v in enumerate(distance):
        if v == k:
            print(i, end = " ")

풀이 설명

• 기본적인 다익스트라 문제였다.

느낀점

• 문제를 풀때 i[0], i[1]인지 헷갈리는 것 같다.
• 이번 문제를 통해서 완벽히 정립할 수 있었다.