목록최소신장트리 (1)

algoqna

[BOJ17472] 다리 만들기 2

17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 모든 섬을 연결하는 다리 길이의 최솟값 == 최소 스패닝 트리(MST)임! 모든 섬을 최소로 연결한다? 섬을 연결할 때 사이클이 생기도록 하면 안된다. 사이클이 생기지 않도록 하고, 최소로 연결한다 MST를 이용하라는 것! 입력에서 섬이 몇개인지를 파악한다. 0이 아닌 경우 num을 증가시켜가며 주변을 bfs로 탐색하여 섬임을 표시해준다 0이 아닌 모든 정점들에 대하여 4방으로 다리를 놓아본다. 다리 놓기에 성공한다면 이 다리 하나하나들이 모..
프로그래밍/기타 문제풀이 2023. 6. 24. 20:29
이전 Prev 1 Next 다음