백준 B17472-다리 만들기2 with 파이썬

문제 17472번: 다리 만들기 2 섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.

섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.

다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다.

섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인... www.acmicpc.net 풀이 해당 문제는 처음에는 풀지 못했다.

다양한 풀이 방식이 있지만, 난 하나도 생각해내지 못했다. 오히려 완전 탐색으로 해결하려고 했다.

그 과정에서 실수를 해결하지 못하고 포기했다가 주말을 이용해 다시 해결한 문제다. 간단히 말하면 섬별 최소 거리를 구한 뒤 프림 알고리즘을 이용해 ...