공부공간

https://www.acmicpc.net/problem/14868 14868번: 문명 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 세계의 크기를 나타내는 정수 N(2 ≤ N ≤ 2,000)과 문명 발상지의 수 K(1 ≤ K ≤ 100,000)가 주어진다. 다음 K줄에는 한 줄에 하나씩 문명 발상지에 해당하는 정사각형의 위치 (x,y)를 나타내는 두 자연수 x와 y가 주어진다. (1 ≤ x,y ≤N) www.acmicpc.net 문명을 bfs로 전파하면서 전체 문명의수가 한개가되는 즉, union-find를 동시에 수행하면서 전체 root가 1개가 되는 시점을 찾으면된다. 편향트리가 될수있기에, rank를 이용하여서 꼭 정리를 해주어야한다. 이러한 disjoint set과 완전탐색이 결합된 문제..

https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX www.acmicpc.net 최적화의 끝.. 문제는 쉽다. MAP에서 . 와 인접한 X는 매초 녹는다. 녹으면서 생기는 .을 통하여 두개의 L이 만날수있는지 물어..