Flood Fill 이란 페인트 기능인데 이는 외부 윤곽선을 따라서 구분되는 영역의 색을 한꺼번에 바꾸는 거고, 이런걸 Flood Fill이라고 부르기도 합니다.
BFS란 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘입니다. 원래 BFS는 그래프라는 자료구조에서 모든 노드를 방문하기 위한 알고리즘입니다. 여기서 말하는 그래프는 우리가 흔히 아는 왼쪽과 같은 형태의 그래프가 아니라 정점과 간선으로 이루어진 자료구조입니다.
BFS 알고리즘에서는 좌표를 담을 큐가 필요합니다. BFS 알고리즘이 시작되면 우선 (0, 0)에 방문했다는 표시를 남기고 해당 칸을 큐에 넣습니다. 이 초기 세팅이 끝난 후에는 큐가 빌 때까지 계속 큐의 front를 빼고 해당 좌표의 상하좌우를 살펴보면서 큐에 넣어주는 작업을 반복하게 됩니다.
BFS의 시간복잡도를 생각해보면 방문 표시를 남기기 때문에 모든 칸은 큐에 1번씩만 들어가게 됩니다. 그렇기 때문에 시간복잡도는 칸이 N개일 때 O(N)이 됩니다. 만약 행이 R개이고 열이 C개이면 O(RC)가 될 것입니다.
BFS의 구현을 다루기 전에 코드에서 쓰이게 될 STL을 하나 소개해드리겠습니다. 바로 utility 헤더에 있는 pair인데, pair를 이용하면 두 자료형을 묶어서 가지고 다닐 수 있습니다. make_pair로 값을 넣어줄 수도 있고, C++11 이상에서는 그냥 중괄호를 써서 쉽게 해결할 수 있습니다.
값의 접근은 각각 first, second를 부름으로서 가능하고 또 pair에는 미리 대소 관계가 설정되어 있어서 편합니다. 알아서 앞쪽의 값을 먼저 비교하고, 이후 뒤쪽의 값을 비교합니다.
거의 BFS의 정석 코드이다.
할 수 있는 실수로는
예시는
1. 기본
방법은 알았으니 구현을 하면 됩니다. 코드를 한 번 감상해보시면 앞의 BFS 코드에서 조금만 변형한걸 알 수 있습니다. 천천히 코드를 분석해보면 말한대로 이중 for문을 돌면서 (i, j)가 BFS의 시작점이 될 수 있는지 확인합니다. 빨간 칸이거나 이미 방문했으면 제외하고, 이후 그 점을 시작점으로 BFS를 돌립니다.
2. 거리측정
구현의 흐름은 일반적인 BFS와 크게 다르지 않습니다. 거리를 저장할 dist 배열을 두고 상하좌우의 칸을 볼 때 값을 잘 넣어주면 됩니다. 그리고 이 배열을 미리 -1로 초기화해두면 굳이 vis 배열을 따로 두지 않아도 방문 여부를 확인할 수 있게 됩니다.
3. 시작점이 여러개일때
지금까지의 상황을 다시 정리해보면 우리는 지금 시작점이 여러 개인 BFS를 돌 수 있어야합니다. 그리고 해결법은 의외로 간단한데, 그냥 모든 시작점을 큐에 넣고 앞에서 한 것과 똑같이 BFS를 돌면 끝입니다. 지금 슬라이드에서의 그림을 보면 파란색은 익지 않은 토마토, 초록색은 익은 토마토, 빨간색은 빈 칸을 의미합니다. 현재 익은 토마토가 2개가 있는데, 그 2개를 큐에 넣어두고 BFS를 돌리면 이렇게 자연스럽게 거리가 잘 구해지게 됩니다.
4. 시작점이 두 종류일때
5. 1차원에서의 BFS
