BOJ :: [11085] 군사 이동

문제

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

11085번: 군사 이동

 

문제 요약

군사 이동 문제는 그래프가 주어지고 특정노드 A에서 노드 B로 이동이 가능한 최대 경로 중에서 최소 비용이 드는 경로(엣지)를 찾는 문제이다.(문제에서는 "경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 최대화하는 경로를 택한다" 라고 되어있어서 이해가 잘 되지 않았다.) 

예를 들어 위와 같은 그래프가 있을 때 노드 1에서 노드 5로 가는 경로를 찾아보면

1 - 2 - 4 - 5와 1 - 4 - 5 두 가지 경로가 존재한다. 이때 첫 번째 경로로 이동하는 경우 비용이 9, 두 번째 경로로 이동하는 경우 비용이 7로 첫 번째 경로로 이동하는 경우가 최대 경로이다. 그리고 최대 경로에서 최소 비용이 드는 엣

지는 1이다.

 

군사 이동 문제의 예제를 그림으로 그려보면 아래 그래프와 같다.

군사 이동 문제의 예시에서는 3번에서 5번으로 이동하는 경로 중 최대 너비를 찾고, 최대 경로 중 최소 너비를 가지는 엣지를 찾으면 16이 나온다. 

풀이

이 문제는 우선순위 큐와 union-find 알고리즘을 사용해서 풀었다.

먼저 우선순위 큐에 모든 경로를 넣어 넓이가 넓은 경로가 먼저 나오도록 한다. 그리고 해당 경로로 그래프를 만들고, 주어진 경로와 같은 그래프에 속해있는지 union-find를 사용하여 확인한다. 만약 같은 그래프에 속해있지 않다면 우선순위 큐에서 경로 만드는 과정을 반복하고, 같은 그래프에 속해있다면 해당 경로가 최대 경로 중 최소 엣지이기 때문에 정답으로 출력한다.

우선순위 큐를 사용하여 너비가 넓은 경로 순서로 나오기 때문에 시작 노드와 종료 노드를 연결하는 최초의 그래프가 최대 경로가 되고, 이 경로에서 마지막으로 나온 경로가 최소 엣지가 된다. 

코드

import sys
import heapq
input = sys.stdin.readline

def union(a, b):
    a = find(a)
    b = find(b)

    if a < b:
        g[b] = a
    else:
        g[a] = b
    return

def find(a):
    if g[a] != a:
        return find(g[a])
    return a

p, w = map(int, input().split())
c, v = map(int, input().split())

g = [i for i in range(p+1)]

pq = []

for i in range(w):
    n, e, width = map(int, input().split())
    heapq.heappush(pq, (-width, n, e))

while pq:
    cost, start, end = heapq.heappop(pq)
    cost = -cost
    union(start, end)
    
    if find(c) == find(v):
        result = cost
        break

print(result)

 

 

작성한 글에 잘못된 부분이나 문제가 있는 경우 댓글에 작성해 주시면 수정하도록 하겠습니다 . 질문도 환영합니다! :)