Loading...

미리보기

전체 14개 스텝 중 5개만 표시

로그인하고 전체 보기

섬 연결하기

보통

Connecting Islands

모든 섬을 다리로 연결하는 최소 비용을 구하는 MST 문제

📊 복잡도

구분	복잡도
최선	O(E log E)
평균	O(E log E)
최악	O(E log E)
공간	O(V)

🏷️ 태그

그래프MSTUnion-Find그리디

📋 문제

섬 연결하기

n개의 섬이 있습니다. 각 섬 사이에 다리를 건설할 수 있으며, 다리마다 건설 비용이 다릅니다. 모든 섬을 연결하는 데 필요한 최소 비용을 구하세요.

1/14

Loading...

🏝️섬 연결하기!

5개의 섬을 다리로 연결해야 합니다. 가장 적은 비용으로 모든 섬을 연결하세요!

섬 연결하기

문제 설명

n개의 섬이 있습니다. 각 섬 사이에 다리를 건설할 수 있으며, 다리마다 건설 비용이 다릅니다. 모든 섬을 연결하는 데 필요한 최소 비용을 구하세요.

입력

섬의 수 n, 건설 가능한 다리 정보 [[from, to, cost], ...]

출력

모든 섬을 연결하는 최소 비용

제약 조건

•1 <= n <= 100
•다리 비용은 1 이상 100 이하

예제

예제 1

입력

5, [[0,1,5], [0,2,3], [1,2,2], [1,3,6], [2,3,4], [2,4,7], [3,4,3]]

출력

설명

비용 2(1-2) + 비용 3(0-2) + 비용 4(2-3) + 비용 3(3-4) = 12

섬 연결하기 | AlgoNote