Flood Fill
그림판의 페인트 기능 마냥 외부 윤곽선을 따라 구분되는 영역의 색을 한번에 바꾸는 등의 기능을 뜻한다. BFS 알고리즘을 사용한 대표적인 기능이다.
Breadth First Search (BFS)
다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘이다.
그래프 자료구조에서 모든 노드를 방문하기 위한 알고리즘이다. 이때 그래프는 정점과 간선으로 이루어진 자료구조이다.
- 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다.
- 큐에서 원소를 꺼내어 상하좌우로 인접한 칸에 대해 3번을 진행한다.
- 해당 칸에 이미 방문한 상태라면 아무것도 하지 않고, 방문하지 않은 상태라면 방문했다는 기록을 남기고 해당 칸을 큐에 넣는다.
- 큐가 빌 때까지 2번을 반복한다.
모든 칸이 큐에 한번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다.
만약 행이 R개이고 열이 C개이면 O(RC)가 된다.
구현
STL의 utility 헤더에 있는 pair를 사용한다. C#에서는Tuple이나 KeyValuePair를 사용하면 되는 것 같다. 또한 BFS는 정석적인 구현이 있어서 이해한 다음 어느정도는 외우는 편이 좋을 것 같다.
int[,] board = new int[,]
{{1,1,1,0,1,0,0,0,0,0},
{1,0,0,0,1,0,0,0,0,0},
{1,1,1,0,1,0,0,0,0,0},
{1,1,0,0,1,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0}};
bool[,] vis = new bool[502, 502];
int n = 7, m = 10;
int[] dx = { 1, 0, -1, 0 };
int[] dy = { 0, 1, 0, -1 };
Queue<KeyValuePair<int, int>> queue = new Queue<KeyValuePair<int, int>>();
vis[0, 0] = true;
queue.Enqueue(new KeyValuePair<int, int>(0, 0));
while(queue.Count > 0)
{
KeyValuePair<int, int> cur = queue.Dequeue();
Console.WriteLine($"( {cur.Key} , {cur.Value} )");
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.Key + dx[dir];
int ny = cur.Value + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (vis[nx, ny] || board[nx, ny] != 1) continue;
vis[nx, ny] = true;
queue.Enqueue(new KeyValuePair<int, int>(nx, ny));
}
}
주의할 점
- 시작점에 방문 표시를 남겨야 한다.
- 큐에 좌표 값을 넣을 때 방문했다는 표시를 남겨야 한다.
- 이웃한 원소가 범위를 벗어났는지 체크를 해야 한다.
연습 문제
1. 백준 1926 : https://www.acmicpc.net/problem/1926
int[,] board = new int[502, 502];
bool[,] vis = new bool[502, 502];
int[] dx = { 1, 0, -1, 0 };
int[] dy = { 0, 1, 0, -1 };
Queue<KeyValuePair<int, int>> queue = new Queue<KeyValuePair<int, int>>();
var input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
for(int i = 0; i < input[0]; i++)
{
var input2 = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
for(int j = 0; j < input[1]; j++)
board[i,j] = input2[j];
}
int answerMax = 0;
int answerNum = 0;
for(int i = 0; i < board.GetLength(0);i++)
{
for (int j = 0; j < board.GetLength(1); j++)
{
if (board[i, j] == 0 || vis[i, j]) continue;
answerNum++;
vis[i, j] = true;
queue.Enqueue(new KeyValuePair<int, int>(i, j));
int area = 0;
while (queue.Count > 0)
{
area++;
KeyValuePair<int, int> cur = queue.Dequeue();
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.Key + dx[dir];
int ny = cur.Value + dy[dir];
if (nx < 0 || nx >= input[0] || ny < 0 || ny >= input[1]) continue;
if (vis[nx, ny] || board[nx, ny] != 1) continue;
vis[nx, ny] = true;
queue.Enqueue(new KeyValuePair<int, int>(nx, ny));
}
}
answerMax = Math.Max(answerMax, area);
}
}
Console.WriteLine(answerNum);
Console.WriteLine(answerMax);
2. 백준 2178 : https://www.acmicpc.net/problem/2178
int[,] board = new int[102, 102];
int[,] vis = new int[102, 102];
int[] dx = { 1, 0, -1, 0 };
int[] dy = { 0, 1, 0, -1 };
Queue<KeyValuePair<int, int>> queue = new Queue<KeyValuePair<int, int>>();
var input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
for(int i = 0; i < input[0]; i++)
{
string input2 = Console.ReadLine();
for (int j = 0; j < input[1]; j++)
board[i,j] = int.Parse(input2[j].ToString());
}
vis[0, 0] = 0;
queue.Enqueue(new KeyValuePair<int, int>(0, 0));
while (queue.Count > 0)
{
KeyValuePair<int, int> cur = queue.Dequeue();
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.Key + dx[dir];
int ny = cur.Value + dy[dir];
if (nx < 0 || nx >= input[0] || ny < 0 || ny >= input[1]) continue;
if (vis[nx, ny] > 0 || board[nx, ny] != 1) continue;
vis[nx, ny] = vis[cur.Key, cur.Value] + 1;
queue.Enqueue(new KeyValuePair<int, int>(nx, ny));
}
}
Console.WriteLine(vis[(input[0] - 1), (input[1] - 1)] + 1);
3. 백준 7576 : https://www.acmicpc.net/problem/7576
int[,] board = new int[1002, 1002];
int[,] dist = new int[1002, 1002];
int[] dx = { 1, 0, -1, 0 };
int[] dy = { 0, 1, 0, -1 };
Queue<KeyValuePair<int, int>> queue = new Queue<KeyValuePair<int, int>>();
var input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
for (int i = 0; i < input[1]; i++)
{
var input2 = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
for (int j = 0; j < input[0]; j++)
{
board[i, j] = input2[j];
if (board[i, j] == 1) queue.Enqueue(new KeyValuePair<int, int>(i, j));
if (board[i, j] == 0) dist[i, j] = -1;
}
}
while (queue.Count > 0)
{
var cur = queue.Dequeue();
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.Key + dx[dir];
int ny = cur.Value + dy[dir];
if (nx < 0 || nx >= board.GetLength(0) || ny < 0 || ny >= board.GetLength(1)) continue;
if (dist[nx, ny] >= 0) continue;
dist[nx, ny] = dist[cur.Key, cur.Value] + 1;
queue.Enqueue(new KeyValuePair<int, int>(nx, ny));
}
}
int ans = 0;
for(int i = 0; i < board.GetLength(0); i++)
{
for(int j = 0; j < board.GetLength(1); j++)
{
if (dist[i, j] == -1)
{
Console.WriteLine(-1);
return;
}
ans = Math.Max(ans, dist[i, j]);
}
}
Console.WriteLine(ans);
4. 백준 4179 : https://www.acmicpc.net/problem/4179
string[,] board = new string[1002, 1002];
int[,] fire = new int[1002, 1002];
int[,] jihoon = new int[1002, 1002];
int[] dx = { 1, 0, -1, 0 };
int[] dy = { 0, 1, 0, -1 };
Queue<KeyValuePair<int, int>> fQueue = new Queue<KeyValuePair<int, int>>();
Queue<KeyValuePair<int, int>> jQueue = new Queue<KeyValuePair<int, int>>();
var input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
for (int i = 0; i < input[0]; i++)
{
var maze = Console.ReadLine();
for (int j = 0; j < input[1]; j++)
{
board[i, j] = maze[j].ToString();
fire[i, j] = -1;
jihoon[i, j] = -1;
if (board[i, j] == "F")
{
fQueue.Enqueue(new KeyValuePair<int, int>(i, j));
fire[i, j] = 0;
}
if (board[i, j] == "J")
{
jQueue.Enqueue(new KeyValuePair<int, int>(i, j));
jihoon[i, j] = 0;
}
}
}
//fire
while (fQueue.Count > 0)
{
var cur = fQueue.Dequeue();
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.Key + dx[dir];
int ny = cur.Value + dy[dir];
if (nx < 0 || nx >= input[0] || ny < 0 || ny >= input[1]) continue;
if (fire[nx, ny] >= 0 || board[nx, ny] == "#" || board[nx, ny] == null) continue;
fire[nx, ny] = fire[cur.Key, cur.Value] + 1;
fQueue.Enqueue(new KeyValuePair<int, int>(nx, ny));
}
}
//jihoon
while (jQueue.Count > 0)
{
var cur = jQueue.Dequeue();
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.Key + dx[dir];
int ny = cur.Value + dy[dir];
if (nx < 0 || nx >= input[0] || ny < 0 || ny >= input[1])
{
Console.WriteLine(jihoon[cur.Key, cur.Value] + 1);
return;
}
if (jihoon[nx, ny] >= 0 || board[nx, ny] == "#" || board[nx, ny] == null) continue;
if (fire[nx, ny] != -1 && fire[nx, ny] <= jihoon[cur.Key, cur.Value] + 1) continue;
jihoon[nx, ny] = jihoon[cur.Key, cur.Value] + 1;
jQueue.Enqueue(new KeyValuePair<int, int>(nx, ny));
}
}
Console.WriteLine("IMPOSSIBLE");
5. 백준 1697 : https://www.acmicpc.net/problem/1697
int[] dist = new int[100002];
int[] dx = { 1, -1 };
Queue<int> queue = new Queue<int>();
Array.Fill(dist, -1);
var input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
dist[input[0]] = 0;
queue.Enqueue(input[0]);
while (dist[input[1]] == -1)
{
var cur = queue.Dequeue();
for (int dir = 0; dir < 3; dir++)
{
int nx;
if (dir == 2)
nx = cur * 2;
else
nx = cur + dx[dir];
if (nx < 0 || nx > 100000) continue;
if (dist[nx] != -1) continue;
dist[nx] = dist[cur] + 1;
queue.Enqueue(nx);
}
}
Console.WriteLine(dist[input[1]]);