BOJ 169571 [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가 될 것입니다. 이 다음엔 진짜 루트 노드를 구하러 갑니다. 무슨 말이냐면 누군가에겐.. 2020. 5. 19. 이전 1 다음
