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 해주면 된다. 아무거나와 해줘도 되는 이유는 잘 관찰하면 어차피 걔네들끼리 이미 같은 분리 집합에 들어 있다는걸 알 수 있기 때문.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 15480 LCA와 쿼리 (0) | 2023.02.14 |
|---|---|
| 백준 1772 정원 정리 (0) | 2023.02.09 |
| 백준 11873 최대 직사각형 (1) | 2023.02.04 |
| 백준 1733 등번호 (0) | 2023.02.03 |
| 백준 25257 Monty's Hall (0) | 2023.02.01 |
