[BOJ]16957번: 체스판 위의 공

 

문제: https://www.acmicpc.net/problem/16957

---

유니온 파인드 문제입니다. 

 

BFS로 문제를 접근한다면 O(R^2*C^2) 으로 시간초과가 납니다.

 

주변에 인접한 칸 중에 가장 작은 칸 A를 루트라고 생각해봅시다.

 

그러면 A칸과 인접한 모든 칸은 A를 부모로 가지고 있습니다 즉, parent[SUM_NODE] = A 이런식입니다.

 

이런식으로 우선 R*C만큼 돌면서 각 노드가 부모로 가지는 노드가 무엇인지 find연산을 해줍니다.

 

그러면 자기 자신이 가장 작은 칸은 parent[NODE] = NODE가 될것이고, 

자기보다 작은 칸이 존재한다면 parent[NODE] = MORE_SMALL_NODE가 될 것입니다.

---

이 다음엔 진짜 루트 노드를 구하러 갑니다.

무슨 말이냐면 누군가에겐 부모인 노드도, 자신이 루트가 아닌, 자신의 부모가 있을 수 있습니다.

 

예를 들면, 

3 2 1 순으로 체스판이 있다면 parent 배열은 1 2 2 (0번인덱스부터) 이와 같은 값을 가지겠네요.

 

즉, 3입장에서는 2가 부모노드이지만, 2의 부모노드는 1이므로 3이 마지막으로 향하는 곳은 1입니다.

 

그래서 전체 체스판에 대해 find를 돌면서 진짜 부모노드로 갱신하도록 합니다.

이에 대한 연산을 재귀적으로 하여 N이 아닌 logN에 수행되도록 해야 합니다.

 

그러면 결국 루트노드들만 남을텐데 그 노드들의 좌표로 공들이 모일 것이고,

자식 노드의 수만큼 그 칸에 공이 존재할 것입니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ16957.cc