사용자 도구

사이트 도구


ps:problems:boj:11085

군사 이동

ps
링크acmicpc.net/…
출처BOJ
문제 번호11085
문제명군사 이동
레벨골드 3
분류

Disjoint Set

시간복잡도O(m*(α(n)+logm))
인풋사이즈n<=1000, m<=50000
사용한 언어Python
제출기록36048KB / 200ms
최고기록144ms
해결날짜2021/10/14

풀이

  • 문제 설명이 살짝 헷갈릴 수 있는데, c에서 v로 가는 경로중에서 가장 좁은 길의 너비가 최대가 되는 경로를 찾으라는 뜻이다
  • 엣지들을 내림차순으로 정렬한 뒤, c와 v가 연결될때까지 하나씩 추가해보다가 연결되는 순간 추가된 엣지를 출력하면 된다. 연결 여부는 Disjoint Set을 사용한다. 엣지를 정렬하고 하나씩 추가하면서 disjoint set을 업데이트 하는 것은 크루스칼 알고리즘의 아이디어와도 살짝 비슷한 느낌이다.
  • 지점의 갯수가 n, 길의 갯수가 m일때, 길을 정렬하는데에 O(mlogm)이 걸리고, 정렬된 길들 최대 m개 추가하면서 연결성을 확인하는 데에는 O(m*α(n))이 걸린다. 총 시간 복잡도는 O(m*(α(n)+logm))

코드

"""Solution code for "BOJ 11085. 군사 이동".

- Problem link: https://www.acmicpc.net/problem/11085
- Solution link: http://www.teferi.net/ps/problems/boj/11085

Tags: [DisjointSet]
"""

import sys
from teflib import disjointset


def main():
    p, w = [int(x) for x in sys.stdin.readline().split()]
    c, v = [int(x) for x in sys.stdin.readline().split()]
    dsu = disjointset.DisjointSet(p)
    walkways = []
    for _ in range(w):
        w_start, w_end, w_width = [int(x) for x in sys.stdin.readline().split()]
        walkways.append((w_width, w_start, w_end))
    walkways.sort(reverse=True)
    for w_width, w_start, w_end in walkways:
        dsu.union(w_start, w_end)
        if dsu.find(c) == dsu.find(v):
            print(w_width)
            break


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
U N​ M A M
 
ps/problems/boj/11085.txt · 마지막으로 수정됨: 2021/10/14 12:04 저자 teferi