17472번: 다리 만들기 2 www.acmicpc.net 이 문제는 섬으로 이루어진 나라를 다리로 연결할 때 다리의 길이의 합의 최솟값을 구하는 문제이다. 단, 다리의 방향이 중간에 바뀌면 안되고, 다리의 길이가 2 이상이어야 한다. 또한 다리가 중간에 다른 섬과 인접한다고 해서 그 섬과 인접하다고 이야기하지 않는다. 또한 다리를 만들 때 반드시 가로 방향이나 세로 방향으로 일직선을 이뤄야 하고 다리의 양 끝은 다리 방향과 같은 방향으로 섬과 인접해야 한다. 이 문제는 결국 분리된 섬들을 최소 길이의 간선들을 이용해 모두 연결시켜야 하므로 최소 스패닝 트리를 만드는 문제라 할 수 있다. 다만, 분리된 섬들이 여러 좌표들의 모임으로 표현되고, 다리는 가로 방향 혹은 세로 방향으로만 설치 가능하며, 다리의..
