Joonas' Note

Joonas' Note

BOJ 1939 - 중량 제한 본문

알고리즘/문제 풀이

BOJ 1939 - 중량 제한

2019. 2. 23. 21:59 joonas

    링크: https://www.acmicpc.net/problem/1939


    문제

    어떤 정점 S에서 다른 정점 E까지 가는 경로에서 등장하는 간선의 가중치의 최대값을 구하는 문제입니다.


    최단 경로를 살피는 것이 아니라, 최대한 무거운 것을 옮기기 위한 다리만 선정한 경로를 만들어야하므로 최소 스패닝 트리의 반대인 최대 스패닝 트리가 떠오릅니다.


    일반적으로 크루스칼 알고리즘은 최소 스패닝 트리를 위해 사용되지만, 이 경우에는 반대로 최대 스패닝 트리를 위해 사용할 수 있을 것 같습니다. (음수 가중치도 없으니 가능해보입니다.)


    연결되지 않은 간선 중 가중치가 가장 큰 간선을 선택하면서 스패닝 트리를 만들어가면, 어떤 정점 S와 다른 정점 E이 같은 "연결된 집합"에 속하는 그 순간에 우리가 원하는 경로가 완성됩니다. 이렇게 완성된 경로는 마치 최장 경로처럼 가능하면 무거운 짐을 옮길 수 있는 다리만 선택하여 만들어진 경로입니다.


    코드



    '알고리즘 > 문제 풀이' 카테고리의 다른 글

    BOJ 9465 - 스티커  (0) 2019.02.24
    BOJ 10472 - 십자뒤집기  (0) 2019.02.23
    BOJ 10799 - 쇠막대기  (0) 2019.02.23
    BOJ 16236 - 아기 상어  (2) 2018.10.30
    BOJ 16235 - 나무 재테크  (0) 2018.10.30
    Comments