너비 우선 탐색(BFS)은 그래프나 그리드에서 최단 경로를 찾거나 연결된 구성 요소를 탐색하는 데 자주 사용되는 강력한 알고리즘입니다. Flood Fill 알고리즘은 특정 시작점에서 인접한 모든 요소들을 탐색하여 변경하는 과정으로, BFS의 대표적인 응용 사례 중 하나입니다. 이 글에서는 BFS를 활용하여 Flood Fill 계열의 문제들을 해결하는 방법을 다룹니다.
1. 이미지 렌더링 (Image Flood Fill)
주어진 이미지에서 특정 픽셀을 시작점으로 하여, 동일한 색상을 가진 인접한 모든 픽셀들을 새로운 색상으로 변경하는 문제입니다. BFS를 사용하면 시작점과 연결된 모든 동일 색상 영역을 효율적으로 탐색할 수 있습니다.
class Solution {
public:
std::vector floodFill(std::vector& imageGrid, int startRow, int startCol, int newColor) {
int oldColor = imageGrid[startRow][startCol];
if (oldColor == newColor) { // 이미 같은 색상이라면 변경할 필요 없음
return imageGrid;
}
int totalRows = imageGrid.size();
int totalCols = imageGrid[0].size();
std::queue> q;
q.push({startRow, startCol});
// 상하좌우 이동을 위한 오프셋
int rowOffsets[] = {1, -1, 0, 0};
int colOffsets[] = {0, 0, 1, -1};
while (!q.empty()) {
auto [currR, currC] = q.front();
q.pop();
imageGrid[currR][currC] = newColor; // 현재 픽셀 색상 변경
for (int i = 0; i < 4; ++i) {
int nextR = currR + rowOffsets[i];
int nextC = currC + colOffsets[i];
// 경계 조건 확인 및 이전 색상과 동일한지 확인
if (nextR >= 0 && nextR < totalRows &&
nextC >= 0 && nextC < totalCols &&
imageGrid[nextR][nextC] == oldColor) {
q.push({nextR, nextC});
}
}
}
return imageGrid;
}
};
문제 분석: 이 문제는 특정 시작점 픽셀부터 BFS 탐색을 시작합니다. 큐에 현재 픽셀을 넣고, 큐가 빌 때까지 다음 작업을 반복합니다. 큐에서 픽셀을 꺼내 새로운 색상으로 변경한 후, 인접한 네 방향의 픽셀들을 확인합니다. 인접 픽셀이 이미지 경계 내에 있고, 변경 전의 원래 색상과 동일하다면, 해당 픽셀을 큐에 추가하여 탐색을 확장합니다. 이미 변경된 픽셀은 다시 큐에 들어가지 않으므로 무한 루프에 빠지지 않습니다.
2. 섬의 개수 (Number of Islands)
이진 그리드(0과 1로 구성)가 주어졌을 때, '1'로 표시된 육지(land)가 상하좌우로 연결되어 형성하는 섬의 총 개수를 세는 문제입니다.
class Solution {
public:
int numIslands(std::vector& islandMap) {
if (islandMap.empty() || islandMap[0].empty()) {
return 0;
}
int islandCount = 0;
int numRows = islandMap.size();
int numCols = islandMap[0].size();
// 방문 여부를 추적하는 배열
std::vector visited(numRows, std::vector<bool>(numCols, false));
std::queue> cellQueue;
int dr[] = {0, 0, 1, -1}; // 행 이동 오프셋
int dc[] = {1, -1, 0, 0}; // 열 이동 오프셋
for (int r = 0; r < numRows; ++r) {
for (int c = 0; c < numCols; ++c) {
// 아직 방문하지 않은 육지를 발견하면 새로운 섬으로 간주
if (islandMap[r][c] == '1' && !visited[r][c]) {
islandCount++;
cellQueue.push({r, c});
visited[r][c] = true; // 시작점 방문 처리
// BFS를 통해 현재 섬의 모든 육지 셀 방문
while (!cellQueue.empty()) {
auto [currR, currC] = cellQueue.front();
cellQueue.pop();
for (int i = 0; i < 4; ++i) {
int nextR = currR + dr[i];
int nextC = currC + dc[i];
// 경계 내에 있고, 육지이며, 아직 방문하지 않은 경우
if (nextR >= 0 && nextR < numRows &&
nextC >= 0 && nextC < numCols &&
islandMap[nextR][nextC] == '1' && !visited[nextR][nextC]) {
cellQueue.push({nextR, nextC});
visited[nextR][nextC] = true; // 큐에 넣기 전 방문 처리
}
}
}
}
}
}
return islandCount;
}
};
문제 분석: 이 문제는 그리드를 순회하면서 아직 방문하지 않은 '1' (육지)을 발견하면 새로운 섬의 시작점으로 간주합니다. 해당 위치에서 BFS를 시작하여 연결된 모든 '1'들을 방문 처리합니다. BFS가 종료되면 하나의 섬 전체를 탐색한 것이므로 섬의 개수를 1 증가시킵니다. `visited` 배열을 사용하여 이미 탐색한 육지 셀은 다시 탐색하지 않도록 하여 중복 계산을 방지합니다.
3. 섬의 최대 면적 (Max Area of Island)
이진 그리드에서 '1'로 표시된 섬들 중 가장 큰 섬의 면적을 찾는 문제입니다. 섬의 면적은 해당 섬을 구성하는 '1'의 개수입니다.
class Solution {
private:
int numRows, numCols;
std::vector visitedCells;
int dr[] = {0, 0, 1, -1};
int dc[] = {1, -1, 0, 0};
int calculateIslandArea(std::vector& mapData, int startR, int startC) {
// 이미 물이거나 방문했다면 면적 없음
if (mapData[startR][startC] == 0 || visitedCells[startR][startC]) {
return 0;
}
std::queue> bfsQueue;
int currentIslandSize = 0;
bfsQueue.push({startR, startC});
visitedCells[startR][startC] = true; // 시작점 방문 처리
while (!bfsQueue.empty()) {
auto [r, c] = bfsQueue.front();
bfsQueue.pop();
currentIslandSize++; // 섬의 셀 개수 증가
for (int i = 0; i < 4; ++i) {
int nextR = r + dr[i];
int nextC = c + dc[i];
// 경계 내에 있고, 육지이며, 아직 방문하지 않은 경우
if (nextR >= 0 && nextR < numRows &&
nextC >= 0 && nextC < numCols &&
mapData[nextR][nextC] == 1 && !visitedCells[nextR][nextC]) {
bfsQueue.push({nextR, nextC});
visitedCells[nextR][nextC] = true; // 큐에 넣기 전 방문 처리
}
}
}
return currentIslandSize;
}
public:
int maxAreaOfIsland(std::vector& grid) {
if (grid.empty() || grid[0].empty()) {
return 0;
}
numRows = grid.size();
numCols = grid[0].size();
visitedCells.assign(numRows, std::vector<bool>(numCols, false)); // 매 테스트 케이스마다 초기화
int maxIslandSize = 0;
for (int r = 0; r < numRows; ++r) {
for (int c = 0; c < numCols; ++c) {
// 육지이고 아직 방문하지 않은 경우에만 BFS 시작
if (grid[r][c] == 1 && !visitedCells[r][c]) {
maxIslandSize = std::max(maxIslandSize, calculateIslandArea(grid, r, c));
}
}
}
return maxIslandSize;
}
};
문제 분석: "섬의 개수" 문제와 유사하게 그리드를 순회합니다. 차이점은 각 섬을 탐색할 때마다 해당 섬을 구성하는 육지 셀의 개수를 세는 것입니다. BFS 함수(`calculateIslandArea`)는 특정 시작점에서부터 연결된 모든 육지 셀을 방문하면서 면적을 계산하고 그 값을 반환합니다. 메인 함수에서는 이 반환값들을 비교하여 가장 큰 면적을 `maxIslandSize`에 저장하고 최종적으로 반환합니다.
4. 둘러싸인 영역 (Surrounded Regions)
문자 'X'와 'O'로 이루어진 2D 보드에서, 'X'에 의해 완전히 둘러싸인 모든 'O' 영역을 'X'로 변경하는 문제입니다. 이때, 보드의 경계에 있는 'O'는 둘러싸인 것으로 간주하지 않습니다.
class Solution {
private:
int boardRows, boardCols;
int deltaR[] = {0, 0, 1, -1};
int deltaC[] = {1, -1, 0, 0};
void exploreBoundaryO(std::vector& gameBoard, int startR, int startC) {
// 'O'가 아니거나 이미 방문(임시 마킹)된 경우 탐색할 필요 없음
if (gameBoard[startR][startC] != 'O') {
return;
}
std::queue> bfsQueue;
bfsQueue.push({startR, startC});
gameBoard[startR][startC] = '#'; // 경계에 연결된 'O'는 임시로 '#'으로 마킹
while (!bfsQueue.empty()) {
auto [currR, currC] = bfsQueue.front();
bfsQueue.pop();
for (int i = 0; i < 4; ++i) {
int nextR = currR + deltaR[i];
int nextC = currC + deltaC[i];
// 경계 내에 있고, 'O'이며, 아직 방문하지 않은 경우
if (nextR >= 0 && nextR < boardRows &&
nextC >= 0 && nextC < boardCols &&
gameBoard[nextR][nextC] == 'O') {
bfsQueue.push({nextR, nextC});
gameBoard[nextR][nextC] = '#'; // 임시 마킹
}
}
}
}
public:
void solve(std::vector& board) {
if (board.empty() || board[0].empty()) {
return;
}
boardRows = board.size();
boardCols = board[0].size();
// 1. 보드의 경계에 있는 'O'와 연결된 모든 'O'를 임시 문자('#')로 변경
// 상단 및 하단 경계 처리
for (int c = 0; c < boardCols; ++c) {
if (board[0][c] == 'O') {
exploreBoundaryO(board, 0, c);
}
if (board[boardRows - 1][c] == 'O') {
exploreBoundaryO(board, boardRows - 1, c);
}
}
// 좌측 및 우측 경계 처리
for (int r = 0; r < boardRows; ++r) {
if (board[r][0] == 'O') {
exploreBoundaryO(board, r, 0);
}
if (board[r][boardCols - 1] == 'O') {
exploreBoundaryO(board, r, boardCols - 1);
}
}
// 2. 보드를 다시 순회하며 상태를 최종적으로 결정
for (int r = 0; r < boardRows; ++r) {
for (int c = 0; c < boardCols; ++c) {
if (board[r][c] == 'O') { // 경계와 연결되지 않은 'O'는 'X'로 변경
board[r][c] = 'X';
} else if (board[r][c] == '#') { // 임시로 마킹했던 '#'는 원래 'O'로 복원
board[r][c] = 'O';
}
}
}
}
};
문제 분석: 이 문제는 경계에 있는 'O'는 둘러싸이지 않는다는 조건 때문에 직접적으로 'O'를 'X'로 바꾸는 것이 어렵습니다. 역발상으로 접근합니다. 먼저 보드의 네 경계선에 위치한 모든 'O'에서 BFS를 시작하여, 이 'O'들과 연결된 모든 'O'들을 임시 문자 (예: '#')로 변경합니다. 이 임시 마킹된 'O'들은 경계와 연결되어 있으므로 'X'로 변경되어서는 안 되는 'O'들입니다. 첫 번째 단계가 완료되면, 보드를 다시 순회합니다. 이때 남아있는 'O'들은 모두 경계와 연결되지 않은, 즉 완전히 둘러싸인 영역이므로 'X'로 변경합니다. 마지막으로 임시 문자('#')로 마킹했던 셀들은 원래의 'O'로 복원합니다.