플러드 필 Flood Fill C++

개요

1. BFS의 특징 및 설계

특징

1. 최단 경로를 찾는다.
2. 인접한 모드 노드를 방문 처리를 하며 탐색 한다.
3. 단계별로 확장 (방문 처리에 값을 할당) 하여 몇 차수만에 왔는지 기록을 한다.

설계

1. 큐(대기열) 및 방문 배열 생성
2. 큐에 시작 노드 삽입 후 큐가 빌 때까지 순환 루프를 진행
3. 큐에서 맨 앞에 있는 노드를 확인 및 추출
4. 현재 노드와 인접한 노드를 탐색하여 존재 한다면 다음 후보를 노드에 추가
5. 2 ~ 4번의 루틴을 반복해 준다.

 

2. Flood Fill

Flood : 홍수, Fill : 채우다. 

퍼져 나가면서 방을 채우듯이 채워 나가며 진행하는 N차원 맵상에서의 BFS

 

Flood Fill 예시 이미지

 

일반적인 BFS에서 노드가 아닌 시작 좌표를 기준으로 방향 배열을 통해 특정 방향으로 탐색을 진행하며, 방문 배열에 방문 체크가 아닌 값을 할당해 준다.

단순히 해당 좌표에 도달했는지 여부를 체크하기 보단 도달하기 까지 걸린 시간을 구한다던가 인접해 있는 노드의 그룹이 몇개인지 등 BFS에 조건이 필요한 경우를 구해야 할 경우 Flood Fill을 사용해 주면 된다.

 

실습

1. 3차원 완전 탐색 문제

대표적인 3차원 거리 탐색 및 완전 탐색 문제로 백준 7569번 토마토 문제가 있다. [링크]

상세 풀이 내용은 하기 링크를 참고 하면 된다. https://zzzz955.tistory.com/157

백준 7569번 토마토 C++, BFS

 

2. 확산 시뮬레이션 문제

추가로, 조건에 따른 확산 여부를 체크하며 완전 탐색을 하는 문제로는 백준 14502번 연구소 문제가 있다. [링크]

마찬가지로 상세 풀이 내용은 하기 링크를 참고 하면 된다. https://zzzz955.tistory.com/155

백준 14502번 연구소 C++