김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 16475 수학 미로 파이썬(Python)

문제 링크

그래프 최단거리 변형 문제.
한 지점에서 다른 지점으로의 최단 거리이므로 다익스트라 알고리즘을 사용했다.
이때, 그래프의 상태가 단순히 위치한 노드로 정의되는 것이 아니라, 1) 위치한 노드, 2) 스위치를 누른 횟수 3) 그래프가 반전된 여부 3가지로 정의된다는 것에 유의해야 한다.
다시 말하자면, 이 문제는 기존 그래프를 p * 2배로 늘린 것이나 다름 없다.
그 외에는 기본 다익스트라 알고리즘과 동일하다.

#!python

from sys import stdin
from heapq import heappush, heappop
input = stdin.readline
INF = float('inf')

# is_trap_node는 해당 노드가 함정 노드인지의 여부를 저장하고 있다
# distance는 3차원 리스트로 선언되어 있는데 distance[0]은 원래 그래프, distance[1]은 함정 간선이 반전된 그래프이다
# distance[0][i][j]는 원래 상태 그래프에서 스위치를 i번 누르고 가는 j번 노드까지의 거리를 의미한다
n, m, k, l, p = map(int, input().split())
graph = [[[] for _ in range(n + 1)] for _ in range(2)]
is_trap_node = [False for _ in range(n + 1)]
distance = [[[INF for _ in range(n + 1)] for _ in range(p)] for _ in range(2)]

for e in map(int, input().split()):
    is_trap_node[e] = True

# 함정 간선이 아닌 간선들은 반전 그래프에도 똑같이 들어간다
for _ in range(m-l):
    a, b, c = map(int, input().split())
    graph[0][a].append((b, c))
    graph[1][a].append((b, c))

# 함정 간선인 간선들은 반전 그래프에는 역방향으로 들어간다
for _ in range(l):
    a, b, c = map(int, input().split())
    graph[0][a].append((b, c))
    graph[1][b].append((a, c))

start, end = map(int, input().split())

# 원래 상태 그래프에서 스위치가 0번 눌린 상태일 때, 시작점까지의 거리는 0
distance[0][0][start] = 0

q = []
# 큐 안의 튜플은 각각 (비용, 노드, 스위치를 누른 횟수, 그래프가 반전되었는지의 여부)를 의미한다
heappush(q, (0, start, 0, 0))

while q:
    cost, node, switch, i = heappop(q)
    if distance[i][switch][node] < cost:
        continue

    # 현재 노드가 함정 노드면 스위치를 누른다
    # 그 이후 스위치를 누른 횟수가 p번이면 함정 간선을 반전시킨 그래프를 사용한다
    next_switch = switch
    next_i = i
    if is_trap_node[node]:
        next_switch = (switch + 1) % p
        if not next_switch:
            next_i = (i + 1) % 2

    # 다익스트라 알고리즘의 핵심
    for next_node, next_cost in graph[next_i][node]:
        if distance[i][switch][node] + next_cost < distance[next_i][next_switch][next_node]:
            distance[next_i][next_switch][next_node] = distance[i][switch][node] + next_cost
            heappush(q, (distance[next_i][next_switch][next_node], next_node, next_switch, next_i))

# 종점 노드까지의 거리 중 가장 작은 것을 취한다
ans = min((distance[i][j][end] for i in range(2) for j in range(p)))
if ans == INF:
    ans = -1
print(ans)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑