알고리즘/백준
백준 6181 플러드 필 (Flood Fill)
6epsilon
2023. 2. 7. 03:53
https://www.acmicpc.net/problem/6181
6181번: 플러드 필 (Flood Fill)
(1,1) - (3,3) - (2,2) 셀은 연결되었으며, (10, 10) 셀은 혼자이다. 섬의 개수는 2개이고, 가장 큰 섬은 크기가 3이다.
www.acmicpc.net
딱봐도 Union-find를 쓰고싶게 생겼다.
https://justicehui.github.io/usaco/2020/12/04/BOJ6181/
백준6181 플러드 필 (Flood Fill)
문제 링크 http://icpc.me/6181
justicehui.github.io
에 나온 것처럼, 45도 돌리면 체비셰프 거리가 된다. x좌표로 스위핑하면서 Set에 y좌표 저장하고, Set 보면서 지금 보고 있는 정점의 Y좌표-D 부터 Y좌표까지 중에서 아무거나와 Union 하고, Y좌표부터 Y좌표+D까지 아무거나와 Union 해주면 된다. 아무거나와 해줘도 되는 이유는 잘 관찰하면 어차피 걔네들끼리 이미 같은 분리 집합에 들어 있다는걸 알 수 있기 때문.