백준 17472. 다리 만들기 2

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

17472번: 다리 만들기 2

 

MST 만들기, 크루스칼 알고리즘:

https://tose33.tistory.com/485

최소 신장 트리(MST), 크루스칼 알고리즘 (kruskal)

 

답을 찾는 방식은 각 섬들 사이의 최단 경로들을 구해놓고, 크루스칼 알고리즘으로 MST를 만드는 것이다. 

 

그러기 위해서는 우선 각 섬들에 고유의 번호를 부여해야 하는데, 이는 bfs로 각 섬들에게 각각의 번호를 부여했다.

 

이제 각 섬들에게는 번호가 생겼다.

그럼 이후에는 섬들 사이의 최단 경로를 구해야 하는데, 하나의 섬마다 그 섬의 모든 칸에 대하여 동서남북으로 한 방향으로 이동하면서 다른 섬을 만나면 시작 섬, 도착 섬, 경로를 기억한다.

이런식으로 모든 섬에 대하여 다른 섬들과의 최단 경로를 구한다.

 

이제 모든 섬들 사이의 최단경로를 구했으니, 크루스칼 알고리즘으로 최소 스패닝 트리를 만들수 있는지 시도해 보면된다. 

크루스칼 알고리즘 종료 후 최소 스패닝 트리가 만들어졌는지 (모든 노드가 서로 이어졌는지) 확인하는 방법은,

두 노드를 연결한 횟수, 즉 Union 연산의 횟수가 모든 노드들의 갯수보다 한개 작은지 확인한다. 

모든 노드들이 서로 연결되어 있다면 그 사의 경로는 노드의 갯수보다 1개 적을것이다. 

즉 Union 연산 횟수 + 1 = 노드의 총 갯수 라면 MST가 성공적으로 만들어진 것이고, 

아니라면 이어지지 못한 노드가 존재하는 것이다. 

 

 

 

 

---

2023.08.05