[BOJ] 백준 17472 다리 만들기 2 (Swift)

문제

https://www.acmicpc.net/problem/17472

17472번: 다리 만들기 2

풀이

구현할게 많았던 문제였습니다.

먼저, 저는 BFS를 사용해 섬에 번호를 부여해주었습니다.

그리고 다리를 놓는 방법에 대해서 고민을 했는데, 다리를 놓으려면 섬의 외각에 있어야 합니다.
섬에 외각에 있다는 것은 자신을 중심으로 상, 하, 좌, 우에 한 뱡향이라도 바다가 있으면 섬의 외각이라고 판별하였습니다.

섬의 좌표에서 상 하 좌 우를 확인하고, 바다가 있다면 다리는 직선으로만 이동하기 때문에 해당 방향을 인덱스로 넣어주었습니다.
0, 1, 2, 3 (동 남 서 북) 순으로 넣어주었습니다.

이제 다리를 놓아야 하는데, 그래프를 확인하면서 바다가 아니라면, (현재 x, y 좌표가 0이 아니라면)
위의 인덱스로 넣어준 방향 (바다로 이동하는 방향)으로 다른 섬을 만나거나, 그래프의 범위를 벗어날 때 까지 이동시켜주었습니다.
이동중에 자신과 같은 섬을 만난다면 break 문으로 탈출하였습니다.

다리의 길이는 1 이상이여아 하므로, 2칸 이상 바다를 이동하고 다른 번호의 섬을 만났다면,
출발 노드, 도착 노드, 비용으로 사용하기 위해 출발 섬 번호, 도착 섬 번호, 다리의 길이를 넣어주었습니다.

이제 이 간선들을 확인하면서 크루스칼 알고리즘을 사용하여서 MST를 만들었습니다.
하지만 주의해야 할 점이 있습니다.

MST가 안되는 경우가 있을 수 있습니다. MST를 이루는 간선의 개수는 노드의 개수 - 1 이므로
이를 확인하고 MST가 안된다면 -1을 출력시켜줍시다.

소스코드

후기

푸는데 은근 시간이 오래걸렸던 문제였습니다..
엄청나게 어렵진 않았는데 구현할게 많은 문제였습니다.

예제는 다 맞았는데 계속 틀렸습니다 판정을 받아서 의아했었는데,
MST가 안되는 경우를 제대로 판별하지 못했었던 문제였습니다.