모든 요소를 탐색하면서 요구사항에 맞게 동작하면 된다.
DFS를 이용하거나 BFS를 사용하는데
1. DFS를 사용할 경우 코드가 간단하지만, map이 크면 메모리 부족이 일어날 수 있고, 디버깅이 어렵다
2. BFS는 맵이 너무 클 경우에 사용한다.
https://chagaun-omija.tistory.com/71
[백준] 2667: 단지번호붙이기
https://www.acmicpc.net/problem/2667 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번
chagaun-omija.tistory.com
여기 있는 이 문제가 Flood Fill의 예시 문제이다.
문제 해설처럼 맵에서 1인 노드를 찾아서 상하좌우에 1인 애들을 카운트해준다.
이 동작을 모든 맵의 요소에 대해 하는데, DFS/BFS를 해주면서 방문표시를 해주면 된다.
특징적인 점은 Flood Fill은 모든 요소들을 탐색해야 하기 때문에 depth 나 breadth를 따로 파라미터로 넘겨줄 필요가 없다.
'컴퓨터기본 > 알고리즘' 카테고리의 다른 글
| 10. Binary Search(이진 탐색) (0) | 2021.09.24 |
|---|---|
| 8. Dynamic Programming (0) | 2021.07.06 |
| 7. 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) (0) | 2021.06.14 |
| 6. 스택 (Stack), 큐 (Queue) (0) | 2021.06.14 |
| 5. 계수 정렬 (Counting Sort) (0) | 2021.06.14 |