[Python] 백준 13905번의 3가지 풀이 방법

문제 링크 : https://www.acmicpc.net/problem/13905

문제에서 (노드 수 N <= 10^5 , 간선 수 M <= 30^5) 이기 때문에 완전 탐색은 시간초과가 난다.

S 에서 E 까지 도달하는데 필요한 간선 가중치를 edge 0, edge 1, .., edge x 라고 했을 때, min(edge 0, edge 1, .., edge x) 가 최대가 되도록 해야한다.

3가지 알고리즘으로 풀면서 공부해봤다.

1. 이분탐색 + BFS
2. 크루스칼 + BFS
3. 다익스트라

1. 이분탐색 + BFS

이게 가장 정석적인 풀이방법이라고 생각이 들었다. 최대한 들고 갈 수 있는 빼빼로 무게를 mid 로 놓고, mid 의 무게를 들고 S 부터 E 까지 갈 수 있는지 BFS로 확인한다.

다리의 무게제한 k <= 10^6 이기 때문에 left = 1, right = 10^6 으로 설정한다.

1~10^6 을 이분탐색 하는데에는 O(log 10^6) = O(1) 이 소요되기 때문에 이분탐색하는 시간은 사실상 무시해도 될 정도고, BFS 돌리는 시간만 고려해주면 되기 때문에 시간초과가 나지 않는다.

import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
S, E = map(int, sys.stdin.readline().split())
edges = [[] for _ in range(N+1)]
answer = 0

for _ in range(M):
    h1, h2, k = map(int, sys.stdin.readline().split())
    edges[h1].append((h2, k))
    edges[h2].append((h1, k))


left = 1
right = 10 ** 6

while left <= right:
    mid = (left + right) // 2
    flag = False
    # BFS
    visit = [False] * (N+1)
    q = deque()
    q.append(S)
    visit[S] = True
    while q:
        now = q.popleft()
        if now == E:
            flag = True
            break
        for node, weight in edges[now]:
            if not visit[node] and weight >= mid:
                q.append(node)
                visit[node] = True

    if flag:
        answer = mid
        left = mid + 1
    else:
        right = mid - 1

print(answer)

2. 크루스칼 + BFS

크루스칼은 Minimum Spanning Tree 를 찾는 알고리즘이다. 근데 이 문제에서는 S 부터 E 까지 가는 경로 간선 가중치를 최대한으로 하고 싶기 때문에, Maximum Spanning Tree 가 필요하다.

크루스칼 알고리즘에서 간선 리스트를 가중치를 기준으로 오름차순 정렬하던 것을 내림차순 정렬하는 걸로만 바꿔주면 구할 수 있었다.

Maximum Spanning Tree 를 만든 후엔, 그 트리에서 S 부터 E 까지 BFS 탐색을 하며 가장 가중치가 낮았던 간선을 기록한다.

크루스칼의 시간복잡도 O(ElogE) = O(10^5) 이기 때문에 시간초과가 나지 않는다.

import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())
S, E = map(int, sys.stdin.readline().split())
parent = [x for x in range(N+1)]
tree = [[] for _ in range(N+1)]
edges = []
answer = 0

for _ in range(M):
    h1, h2, k = map(int, sys.stdin.readline().split())
    edges.append((h1, h2, k))

def find_parent(x):
    if parent[x] == x:
        return x
    parent[x] = find_parent(parent[x])
    return parent[x]

def union(x, y):
    px = find_parent(x)
    py = find_parent(y)
    parent[max(px, py)] = min(px, py)

# 크루스칼
edges.sort(key=lambda x: -x[2])
for edge in edges:
    if find_parent(edge[0]) == find_parent(edge[1]):
        continue
    union(edge[0], edge[1])
    tree[edge[0]].append((edge[1], edge[2]))
    tree[edge[1]].append((edge[0], edge[2]))

visit = [False] * (N+1)
q = deque()
q.append((S, 10**6))
visit[S] = True

while q:
    now, cookie = q.popleft()
    if now == E:
        answer = cookie
        break
    for x, weight in tree[now]:
        if not visit[x]:
            cookie = min(cookie, weight)
            q.append((x, cookie))
            visit[x] = True

print(answer)

3. 다익스트라

다익스트라는 최단 거리 테이블을 만들고 갱신해나가는 알고리즘이다. 이 문제에서는 최단 거리 테이블이 아닌, 그 노드까지 들고 갈 수 있는 최대 빼빼로 테이블을 갱신해 나가는 걸로 변형을 해서 풀 수 있었다.

힙을 이용한 다익스트라의 시간복잡도는 O(ElogV) = O(10^5) 이기 때문에 시간초과가 나지 않는다.

import sys
import heapq
INF = sys.maxsize
N, M = map(int, sys.stdin.readline().split())
s, e = map(int, sys.stdin.readline().split())
edges = [[] for _ in range(N+1)]
answer = 0
distance = [0] * (N+1)

for _ in range(M):
    h1, h2, k = map(int, sys.stdin.readline().split())
    edges[h1].append((h2, k))
    edges[h2].append((h1, k))

h = []
heapq.heappush(h, (-INF, s))
distance[s] = INF

while h:
    dist, now = heapq.heappop(h)
    dist = - dist
    if distance[now] > dist:
        continue
    for node, d in edges[now]:
        cost = min(dist, d)
        if cost > distance[node]:
            distance[node] = cost
            heapq.heappush(h, (-cost, node))

print(distance[e])