[백준/Python]23286: 허들 넘기

문제

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

백준 문제집 - 0x1C강 - 플로이드 알고리즘

알고리즘: 그래프 이론, 최단 경로, 데이크스트라, 플로이드-워셜

---

풀이

 

출발노드를 A, 도착노드를 B라 했을때 A에서 B로 가는 경로는 여러가지가 될 것이다.
각 경로(A-K-B)에서 가장 높은 허들을 h라 했을때, h1, h2, h3... 중 가장 작은 값이 A-B 경로의 값이 되는것이다.

 

만약 graph[A][K]의 높이가 3, graph[K][B]의 높이가 6이라면 A-K-B의 경로는 6이 된다.
이런식으로 모든 정점 K를 중간 노드로 두고 각 경로마다 가장 높은 허들을 체크한다.
(기존 graph[A][B]값이 4라면 4 < 6이니 갱신하지 않고 그대로 두는 식.)

 

참고로 이 문제... 예전에 플로이드워셜 + Python3로 제출했을때는 시간초과 판정을 받았다.
풀이글을 작성하며 좀 더 다듬어서 다시 제출해보니 통과된다. 기준이 완화된듯?

하지만 다익스트라를 사용하는 풀이보다는 느리다. 사실 이 문제는 다익스트라를 사용하면 빠른 시간으로 통과할 수 있다!
(플로이드 워셜 사용시: 2056ms / 다익스트라 사용시: 600ms)

 

문제 자체는 플로이드 워셜 유형이지만, 노드는 최대 300개가 주어질 수 있는 반면에 간선은 최대 25,000개만 주어진다.
모든 노드가 이어져있다고 가정했을때의 간선 수는 90,000개 이므로 실제보다 훨씬 적은 값이 주어지는 셈이다.

 

1. 다익스트라 사용 풀이 (heapq)

일단 간선 정보 저장 / 계산값 갱신을 분리해야한다.

나는 간선 정보 저장은 2차원 딕셔너리({a: {b: h}})를, 갱신은 2차원 리스트를 사용했다. 둘 다 리스트로 관리해도 상관은 없지만 위에서 말했다시피 간선 갯수는 노드 수에 비해 적으므로 딕셔너리를 활용하는게 더 효율적이다.

 

그리고 모든 노드를 시작점으로 두며 다익스트라를 실행한다. 초기 힙(최소힙)에는 (0, 시작노드)가 들어있다.
힙이 빌 때까지 아래 과정을 반복한다.
(graph = 초기 간선 값 / heights = A-B 허들 높이 계산값)

1. (높이, 노드)를 힙에서 꺼낸다.
2. 만약 꺼낸 높이값이 heights[시작점][노드]보다 크다면, 이미 확인한 노드이므로 넘어간다.
3. 아니라면 노드와 연결된 간선 정보들을 확인한다.
   • 현재 노드에서 갈 수 있는 노드를 nxt라고 했을때, graph[노드][nxt]값과 현재 높이 값을 비교한다.
   • 둘 중 더 큰값을 최대 허들 높이로 선정. (최대 허들 높이)
   • 만약 이 값이 기존의 heights[시작노드][nxt]값보다 작다면 갱신, 힙에 추가. (최소값)

힙에 들어있는 높이값은 시작점에서 현재 노드까지 가는 경로들 중에서 "가장 높은 허들"을 의미한다.
하지만 최소 힙에 저장했으니 pop되는 값은 여러개의 시작노드 → 현재노드 경로 중 가장 최소의 최대 허들 높이값이 되는것이다.
같은 노드에 도달하더라도 어떤 경로로 왔느냐에 따라 최대 허들 높이가 달라지는거다.
pop한 높이값과 nxt 사이의 허들 높이값을 비교해서 더 높은 허들을 new_h로 결정하고, 이 값이 기존의 시작노드 → nxt 경로의 높이값보다 작으면 갱신하는것!

 

전체 코드

# 메모리: 37452KB / 시간: 600ms
from sys import stdin
from collections import defaultdict
from heapq import heappop, heappush


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

N, M, T = map(int, input().split())
# 2차원 딕셔너리 생성
# graph[a][b] = {a: {b: 허들 높이}}
graph = defaultdict(dict)

for _ in range(M):
    u, v, h = map(int, input().split())
    graph[u][v] = h


def dijkstra(start):
    queue = []
    heappush(queue, (0, start))

    while queue:
        curr_h, curr = heappop(queue)

        if heights[start][curr] < curr_h:
            continue

        for nxt, h in graph[curr].items():
            new_h = max(h, curr_h)
            if new_h < heights[start][nxt]:
                heights[start][nxt] = new_h
                heappush(queue, (new_h, nxt))


heights = [[INF] * (N+1) for _ in range(N+1)]

# 다익스트라로 모든 노드를 시작점으로 두고 최단경로 구하기
for i in range(1, N+1):
    heights[i][i] = 0
    dijkstra(i)

for _ in range(T):
    s, e = map(int, input().split())
    ret = heights[s][e]
    print(ret if ret != INF else -1)

---

2. 플로이드-워셜 사용 풀이

플로이드를 사용하면 비교적 간단해진다.
k-i-j로 플로이드 워셜을 수행하면서 필요한 조건만 체크해주면 된다.

1. graph[i][k]와 graph[k][j]의 값이 INF인지 확인한다.
   • INF라면 불가능한 경로이므로 넘어감.
2. graph[i][k]의 허들 높이, graph[k][j]의 허들 높이 중 더 큰 값을 선택. (최대 허들 높이)
3. 만약 이 값이 기존의 graph[i][j]값보다 작다면 갱신한다. (최소값)

 

전체 코드

# 메모리: 33432KB / 시간: 2056ms
from sys import stdin


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

def main():
    N, M, T = map(int, input().split())
    graph = [[INF if i != j else 0 for j in range(N)] for i in range(N)]

    for _ in range(M):
        u, v, h = map(int, input().split())
        graph[u-1][v-1] = h

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if graph[i][k] == INF or graph[k][j] == INF:
                    continue

                # i-k 경로의 허들과 k-j 경로의 허들 중 더 높은값
                max_h = max(graph[i][k], graph[k][j])
                if graph[i][j] > max_h:
                    graph[i][j] = max_h

    for _ in range(T):
        s, e = map(int, input().split())
        print(graph[s-1][e-1] if graph[s-1][e-1] != INF else -1)


main()

---

그래도 직관적으로 이해하기 쉬운건 플로이드 워셜이다. (흑흑)