[Python] [BOJ] 군사이동(11085)

💡 문제 해결

1. 입력으로 받은 길에 대한 정보를 너비를 기준으로 최대힙 생성
2. 최대힙의 값을 빼내며 경로압축 진행
3. 만약 출발지와 목적지가 하나의 부모노드를 가지게 된다면 하나의 경로로 이어졌다는 의미이므로 반복문 종료
4. 마지막에 빼낸 값이 경로 중 가장 좁은 길의 너비

📌 군사가 가장 많이 이동할 수 있는 경로 중 가장 작은 길의 너비를 뽑는다는 아이디어를 떠올리기 어려웠던 문제
📌 최단 이동 거리가 필요한게 아니라 가장 많은 군사가 이동할 수 있는 경로라는 것이 중요 !
📌 최대힙으로 생성 후 최대값 순서로 뽑아 경로를 연결하며, 출발지와 목적지가 한 경로로 이어졌을 때 마지막으로 뽑은 값이 경로 중 최소값이 될 수 밖에 없다

🧾 문제 설명

전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다.
Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 
모든 길은 양방향이며, 각 길마다 너비가 존재하여 이에 비례하는 수의 군사가 지나갈 수 있습니다.

Baekjoon World의 국왕은 군사들이 뭉치는 것이 유리하다고 생각해서, 
미리 Cube World로 가는 경로를 정해 두고 그 경로로만 모든 군사를 보냈습니다. 
Baekjoon World의 국왕은 총명해서, 경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 최대화하는 경로를 택했습니다.

그런데 전쟁 때문에 어느 길로 보냈는지에 대한 기록이 불타 없어져 버렸습니다. 
전쟁사를 완성하려면 이 기록이 꼭 필요합니다. 
위대한 과학자인 당신이 다시 복구해 주세요.

문제보기

🖨 입출력

📝 풀이

import sys, heapq

input = sys.stdin.readline

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

    parent[x] = find(parent[x])
    return parent[x]


def union(x, y):
    x, y = find(x), find(y)

    if x == y: return False

    if rank[x] < rank[y]:
        x, y = y, x

    parent[y] = x

    if rank[x] == rank[y]:
        rank[x] += 1
    return True



p, w = map(int, input().split())
c, v = map(int, input().split())
heap = []
for _ in range(w):
    start, end, width = map(int, input().split())
    heapq.heappush(heap, (-width, start, end))

parent = [i for i in range(p)]
rank = [1] * p

answer = 0
while heap:
    width, start, end = heapq.heappop(heap)
    if union(start, end):
        if find(c) == find(v):
            answer = -width
            break

print(answer)

• 출처: BAEKJOON Online Judge
• 링크: https://www.acmicpc.net/problem/11085