MST

문제이해 문제가 호흡이 긴데 요약하자면 1로 된 섬과 0으로 된 바다로 이루어진 매트릭스가 주어질 때 최소 비용으로 그 섬을 모두 연결하는 문제이다. 다만, 다리는 직선이어야 하고 길이가 2 이상 이어야 한다. 계획 일단 이문제의 핵심은 모든 섬을 최소비용으로 연결해야 한다는 점이다. 이 점만 본다면 일반 최소신장트리(MST) 문제와 다르지 않다. 크루스칼을 쓰면서 섬을 추가하면 된다. 다만 그러기 위해서는 각 섬과의 다리 개수와 길이, 섬의 개수가 필요하다. 따라서, 첫 번째로 주어지는 매트릭스에서 그러한 정보를 추출해야 한다. 이 문제의 대략적인 순서는 아래와 같아야 한다. 1. 매트릭스에서 섬위치와 개수 파악 2. 매트릭스에서 다리 개수와 길이 추출 3. 크루스칼 먼저 매트릭스에서 섬이 같은 섬인지..