백준 16398 파이썬1 16398. 행성 연결 (Python) 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 풀이 크루스칼 알고리즘을 사용하여 최소 스패닝 트리를 만들면 된다. 크루스칼 알고리즘에 대해서 간단히 설명하자면 입력으로 주어진 간선 정보를 비용을 기준으로 오름차순 정렬한다(우선수위 큐를 사용하면 된다). 비용이 낮은 순으로 간선을 꺼내어 해당 간선을 사용했을 때 그래프에 사이클이 발생하는지 체크한다. 사이클이 발생하지 않을때만 해당 간선을 사용하여 그래프를 완성해 나간다. 이를 반복하여 총 N개의 정점이 있을 때 N-1개의 간선을 사용했다면 모든 정점이 사이클.. 2022. 6. 23. 이전 1 다음
