읍내리 까치골
[C++] 2차원 배열 기반 BFS (기초) (+ 백준 1012번 풀이) 본문
알고리즘을 공부할 때 그래프 구조에서 사용하는 대표적 알고리즘으로 DFS와 BFS가 있습니다. Depth First Search, Breadth First Search의 약자로 풀이하면 깊이 우선 탐색, 너비 우선 탐색이라 부를 수 있습니다.
두 알고리즘은 원리 자체는 동일하다 볼 수 있고, 단지 노드 탐색에 있어 Queue에서 넣고 꺼내는 순서의 차이가 있다고 생각하면 될 것 같습니다.
BFS 하면 가장 많이 보이는 그림입니다. Root는 탐색을 시작하는 지점이며 레벨 0으로 간주하겠습니다. BFS의 동작은 해당 레벨의 노드를 모두 탐색하면 다음 레벨의 노드를 탐색합니다. 그림에서 보시다시피 레벨 1의 노드 두 개 (1, 2번)을 모두 탐색한 후에는 레벨 2로 넘어가서 탐색을 계속합니다.
이러한 원리로 "너비 우선 탐색"이라고 불리는 것이고, 동일 깊이의 노드를 모두 탐색한 후 다음 깊이의 노드를 탐색한다는 핵심만 기억하시면 될 것 같습니다.
2차원 배열 기반 BFS 개념
주제가 조금 생소하실 수도 있을 것 같습니다. 이것은 그래프와 탐색에 대한 이해를 묻는 문제에서 2차원 배열 형태를 준 뒤에 탐색하여 결과를 도출하는 알고리즘 문제에서 주로 사용하는 방법입니다. 아래 예시를 보시겠습니다.
2차원 배열 예시 (초기 상태)
| Start | |||||
만약 상, 하, 좌, 우 4방향으로만 탐색한다고 (대각선은 고려하지 않고 변이 맞닿은 부분만 탐색) 가정해보겠습니다. 그렇다면 변으로 맞닿은 인접 칸들은 한 번에 넘어갈 수 있으니 거리가 1이 될 것입니다.
2차원 배열 예시 (깊이 1)
| 1 | |||||
| 1 | Start | 1 | |||
| 1 |
위 표와 같이 깊이 레벨 1번을 탐색하면 4개의 노드가 탐색될 것입니다. 상, 하, 좌, 우 4방향으로 탐색한 결과입니다. 그 다음 배열의 모든 칸을 탐색해보겠습니다.
2차원 배열 예시 (탐색 완료)
| 6 | 5 | 4 | 3 | 4 | 5 |
| 5 | 4 | 3 | 2 | 3 | 4 |
| 4 | 3 | 2 | 1 | 2 | 3 |
| 3 | 2 | 1 | Start | 1 | 2 |
| 4 | 3 | 2 | 1 | 2 | 3 |
이렇게 모든 칸을 탐색해보면 사각형 모양으로 퍼져나가듯 탐색하는 것을 볼 수 있습니다.
2차원 배열 기반 BFS 구현
그렇다면 배열 기반 BFS의 구현은 어떻게 해야 할까요? 깊이 정보가 필요가 없다면 상, 하, 좌, 우 방향으로 탐색 가능한 노드인지 확인하고 탐색 가능하다면 탐색했다는 표시를 하면 됩니다. 깊이 정보가 필요하다면 Queue 구조를 활용하여 깊이 레벨을 함께 넣어야 하는데 이 부분은 다음 기회에 14940번 :: 쉬운 최단거리 문제와 함께 알아보겠습니다.
이번에는 단순하게 배열 안에서 탐색 가능한 모든 노드를 탐색해보는 방식으로 알아보겠습니다. 아래 예시 그림을 확인해보겠습니다.
만약 (0, 0) 위치에서 탐색을 하는데 (0, 1) 위치가 이미 탐색이 되었다고 가정해보겠습니다. 2차원 배열에서 상, 하, 좌, 우로 움직인다고 가정했으므로, 현재 탐색중인 노드의 인덱스를 (x, y)로 표현한다고 하면 인접 4방향 노드의 인덱스는 (x-1, y), (x+1, y), (x, y-1), (x, y+1)이라고 볼 수 있겠습니다.
이렇게 4방향으로 탐색을 할 때 중요한 조건이 있습니다. 첫 번째는 접근할 수 있는 인덱스인가? 입니다. 배열의 크기를 초과하는 인덱스이거나, 0 미만 음수가 나오면 접근 불가능한 인덱스이므로 액세스 위반 오류가 뜨게 됩니다. 두 번째는 탐색이 되지 않은 노드인가? 입니다. 이미 탐색이 완료된 노드라면 건너뛰어야 합니다. BFS 또는 DFS 알고리즘은 재귀 구조로 이루어져있는데 탐색이 완료되었다고 표시된 것은 해당 노드에서도 이미 BFS 재귀가 이루어진 것이므로 다시 접근하도록 코드를 작성하면 무한 루프에 빠질 위험이 있습니다.
이 두 가지 조건을 따져서 BFS 재귀 함수를 작성해보면 아래와 같은 형태가 될 것입니다.
bool **matrix;
int row, col;
void bfs(int x, int y){
matrix[x][y] = true;
// 4-ways bfs
if(x > 0){
if(matrix[x-1][y] == false)
bfs(x-1, y);
}
if(x < col - 1){
if(matrix[x+1][y] == false)
bfs(x+1, y);
}
if(y > 0){
if(matrix[x][y-1] == false)
bfs(x, y-1);
}
if(y < row - 1) {
if(matrix[x][y+1] == false)
bfs(x, y+1);
}
}
백준 1012번 문제 :: 유기농 배추
문제 링크 : https://www.acmicpc.net/problem/1012
1012번: 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에
www.acmicpc.net
2차원 배열 기반 BFS 알고리즘을 연습하기에 좋은 문제입니다. 입력 예제를 보면 2차원 배열의 가로와 세로 크기, 그리고 탐색해야 할 노드 개수와 노드의 좌표들이 입력이 됩니다. 입력 데이터에서 지정된 노드들 끼리 인접한 그룹이 몇 개인지 (즉 배열에서 표현된 노드들이 몇 개의 그룹을 가지고 있는지) 출력하는 문제입니다.
풀이
입력된 예제를 2차원 배열에 표현하면 아래와 같습니다.
| O | O | ||||||||
| O | |||||||||
| O | |||||||||
| O | |||||||||
| O | O | O | O | O | |||||
| O | O | O | O | ||||||
| O | O | O | |||||||
문제의 조건을 바탕으로 인접한 노드들의 그룹의 개수를 살펴본다면 총 5개의 그룹이 될 것입니다. 그렇다면 이렇게 인접한 노드들의 그룹은 어떤 기준으로 판단해야 할까요? 아래와 같은 분석을 통해 문제를 풀어보겠습니다.
- 탐색되지 않은 노드를 발견하여 BFS 알고리즘을 시행하면 해당 노드와 인접한 노드들은 모두 탐색이 완료된 것으로 표시될 것이다.
- BFS의 재귀가 다 끝나면 해당 그룹은 파악이 완료된 것이다 => 그룹 개수 카운트를 하나 늘린다.
- 아직 탐색되지 않은 노드를 찾아 다시 BFS 알고리즘을 반복한다.
- 2차원 배열의 시작점부터 끝점까지 2중 반복문을 돌려 모든 노드를 탐색하면 모든 그룹이 다 카운트 될 것이다.
이러한 분석을 바탕으로 해당 문제 풀이를 위한 코드를 작성해보았습니다. 독자 분들께서 실행 결과를 확인할 수 있도록 별도로 printMatrix() 함수를 작성하여 출력하도록 설정하였습니다.
#include <iostream>
#include <queue>
using namespace std;
#define endl '\n'
// baekjoon 1012
int **cabbage; // is Cabbage
int row, col;
void bfs(int x, int y, int areaNum){
cabbage[x][y] = areaNum;
// 4-ways bfs
if(x > 0){
if(cabbage[x-1][y] == -1)
bfs(x-1, y, areaNum);
}
if(x < col - 1){
if(cabbage[x+1][y] == -1)
bfs(x+1, y, areaNum);
}
if(y > 0){
if(cabbage[x][y-1] == -1)
bfs(x, y-1, areaNum);
}
if(y < row - 1) {
if(cabbage[x][y+1] == -1)
bfs(x, y + 1, areaNum);
}
}
void printMatrix(){
for(int i=0; i<row; i++){
for(int j=0; j<col; j++){
printf("%2d ", cabbage[j][i]);
}
cout<<endl;
}
}
int main() {
cin.tie(nullptr);
cout.tie(nullptr);
//ios_base::sync_with_stdio(false);
int cases, x, y, numOfCabbage;
cin>>cases;
// loop for cases===============================
for(int c=0; c<cases; c++){
cin>>col>>row>>numOfCabbage;
int numOfArea = 0;
// init Matrix
cabbage = new int* [col];
for(int i=0; i<col; i++){
cabbage[i] = new int[row];
for(int j=0; j<row; j++)
cabbage[i][j] = 0;
}
// get Cabbage Position
for(int i=0; i<numOfCabbage; i++){
cin>>x>>y;
cabbage[x][y] = -1;
}
// find New Area
for(int i=0; i<col; i++){
for(int j=0; j<row; j++){
if(cabbage[i][j] == -1) {
bfs(i, j, ++numOfArea);
}
}
}
// return memory
cout<<numOfArea<<endl;
printMatrix();
for(int i=0; i<col; i++){
delete[] cabbage[i];
}
delete[] cabbage;
} //end of cases loop =============================
return 0;
}
예제 1번의 첫번째 테스트케이스에 대한 실행 결과 (배열 출력을 임의로 출력)
5
1 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 3 0 0 0 0 0
0 0 0 0 3 0 0 0 0 0
0 0 2 2 0 0 0 5 5 5
0 0 0 0 4 0 0 5 5 5
0 0 0 0 0 0 0 5 5 5
0 0 0 0 0 0 0 0 0 0
그룹 번호를 지정하여 출력함으로써 인접 노드 그룹 개수가 카운트 됨을 표현하였습니다. 비록 Queue를 사용하지 않은 간단한 BFS였지만 BFS의 원리를 공부하기에는 괜찮은 문제라고 생각했습니다.
이렇게 2차원 배열 기반 간단한 BFS를 알아봤습니다. 다음번에는 깊이 레벨과 함께 Queue 구조를 사용하는 조금 더 심화된 BFS에 대하여 알아보겠습니다.
긴 글 읽어주셔서 감사합니다.