[Algorithm] DFS와 BFS 기본과 예제 문제
BFS와 DFS를 공부해 볼 수 있는 간단한 문제를 풀어보자.
환경 및 선수조건
- C++
- BFS와 DFS의 정의 및 구현 방법 기초([Algorithm] C++에서 그래프 탐색(DFS와 BFS) 구현하기)
문제
문제 링크
- 백준 2667번 문제
- 문제 링크: https://www.acmicpc.net/problem/2667
- 문제: <그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.
접근법
- 지도에서 하나하나 조사하면서 집을 발견하면 단지로 정의하고 집의 수를 세는 방법으로 풀이가 가능합니다.
- 하나하나 조사를 해야하기 때문에 완전탐색으로 생각할 수 있습니다.
- 단지 안에서 집의 수를 세는건 주변으로 뻗어 나가는 방법을 사용하기 때문에 BFS나 DFS를 통해서 4방향으로 탐색을 진행하면 됨을 알 수 있습니다.
풀이법
- 전체의 지도를 돌면서 집이 있는지 확인하다.
- 집(배열의 값 == 1)을 발견하면 단지로 정의하고 ID를 부여한다.
- BFS 또는 DFS 탐색을 통해서 해당 단지의 집의 수를 구한다.
- 해당 단지의 집의 수를 다 구하게 되면 해당 집의 ID를 인덱스로 하는 배열에 추가해준다.
- 전체 지도의 탐색이 다 끝나면 배열을 오름차순으로 정렬하고 출력한다.
완전탐색이란?
정의
완전탐색(Bruete Force): 가능한 모든 경우의 수를 다 시도해 답을 찾는 방법- 정확하고 확실하게 답을 찾을 수 있다는 장점이 있지만 시간이 오래 걸린다는 단점이 있다.
- 예시: 1부터 n까지의 수를 모두 더하기, 난수에서 배열에서 특정한 수 찾기 등등…
BFS와 DFS
- 해당내용은 [Algorithm] C++에서 그래프 탐색(DFS와 BFS) 구현하기의 내용과 동일합니다.
개념
- DFS(깊이우선탐색): 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색
- BFS(너비우선탐색): 현재 정점에 연결된 가까운 점들부터 탐색
- 위의 이미지를 참고하시면 비교가 쉽습니다. 해당 번호 순서대로 탐색을 합니다.
방법
- DFS: 스택 또는 재귀함수로 구현
- BFS: 큐를 이용해서 구현
풀이코드
DFS(Recursion)
- 재귀함수를 이용한 DFS 풀이
// DFS - Recursion
void dfs_recursion(int x, int y) {
// 함수에 들어왔으면 -> 방문으로 표시
visited[x][y] = true;
// 해당 단지의 집의 수를 증가시킴
groups[group_id]++;
// 해당 위치의 주변을 확인
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 지도를 벗어나지 않고
if(0 <= nx && nx < n && 0 <= ny && ny < n){
// 집이면서 방문하지 않았다면 -> 방문
if(map[nx][ny] == 1 && visited[nx][ny] == false){
dfs_recursion(nx, ny);
}
}
}
}
DFS(Stack)
- 스택을 이용한 DFS 풀이
// DFS - Stack
void dfs_stack(int x, int y) {
stack< pair<int,int> > s; // 이용할 스택, (x,y) -> (행, 열)
s.push(make_pair(x,y)); // pair를 만들어서 stack에 넣습니다.
// 처음 x,y를 방문 했기때문에
visited[x][y] = true;
groups[group_id]++;
while(!s.empty()){
// 스택의 top 원소 꺼내기
x = s.top().first;
y = s.top().second;
s.pop();
// 해당 위치의 주변을 확인
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 지도를 벗어나지 않고
if(0 <= nx && nx < n && 0 <= ny && ny < n){
// 집이면서 방문하지 않았다면 -> 방문
if(map[nx][ny] == 1 && visited[nx][ny] == false){
visited[nx][ny]=true;
// 해당 단지의 집의 수를 증가시킴
groups[group_id]++;
s.push(make_pair(x,y)); // push하는 경우이기 때문에 현재 위치도 넣어준다.
s.push(make_pair(nx,ny)); // 스택에 현재 nx,ny도 푸시
}
}
}
}
}
BFS(Queue)
- 큐를 이용한 DFS 풀이
// BFS
void bfs(int x, int y){
queue< pair<int,int> > q; // 이용할 큐, (x,y) -> (행, 열)
q.push(make_pair(x,y)); // pair를 만들어서 queue에 넣습니다.
// 처음 x,y를 방문 했기때문에
visited[x][y] = true;
groups[group_id]++;
while(!q.empty()){
// 큐의 현재 원소를 꺼내기
x = q.front().first;
y = q.front().second;
q.pop();
// 해당 위치의 주변을 확인
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 지도를 벗어나지 않고
if(0 <= nx && nx < n && 0 <= ny && ny < n){
// 집이면서 방문하지 않았다면 -> 방문
if(map[nx][ny] == 1 && visited[nx][ny] == false){
visited[nx][ny]=true;
// 해당 단지의 집의 수를 증가시킴
groups[group_id]++;
// 큐에 현재 nx,ny를 추가
q.push(make_pair(nx,ny));
}
}
}
}
}
전체 코드
#include <iostream>
#include <stdio.h>
#include <queue>
#include <stack>
#include <algorithm>
#define MAX_SIZE 25
using namespace std;
// 위, 오른, 아래, 왼
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int n; // 행과 열의 수
int group_id; // 단지의 번호로 첫번째 단지부터 1로 시작
int groups[MAX_SIZE * MAX_SIZE]; // 각 단지별 집의 수
int map[MAX_SIZE][MAX_SIZE]; // 지도
bool visited[MAX_SIZE][MAX_SIZE]; // 방문했는지를 표시하는 지도
// DFS - Recursion
void dfs_recursion(int x, int y) {
// 함수에 들어왔으면 -> 방문으로 표시
visited[x][y] = true;
// 해당 단지의 집의 수를 증가시킴
groups[group_id]++;
// 해당 위치의 주변을 확인
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 지도를 벗어나지 않고
if(0 <= nx && nx < n && 0 <= ny && ny < n){
// 집이면서 방문하지 않았다면 -> 방문
if(map[nx][ny] == 1 && visited[nx][ny] == false){
dfs_recursion(nx, ny);
}
}
}
}
// DFS - Stack
void dfs_stack(int x, int y) {
stack< pair<int,int> > s; // 이용할 스택, (x,y) -> (행, 열)
s.push(make_pair(x,y)); // pair를 만들어서 stack에 넣습니다.
// 처음 x,y를 방문 했기때문에
visited[x][y] = true;
groups[group_id]++;
while(!s.empty()){
// 스택의 top 원소 꺼내기
x = s.top().first;
y = s.top().second;
s.pop();
// 해당 위치의 주변을 확인
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 지도를 벗어나지 않고
if(0 <= nx && nx < n && 0 <= ny && ny < n){
// 집이면서 방문하지 않았다면 -> 방문
if(map[nx][ny] == 1 && visited[nx][ny] == false){
visited[nx][ny]=true;
// 해당 단지의 집의 수를 증가시킴
groups[group_id]++;
s.push(make_pair(x,y)); // push하는 경우이기 때문에 현재 위치도 넣어준다.
s.push(make_pair(nx,ny)); // 스택에 현재 nx,ny도 푸시
}
}
}
}
}
// BFS
void bfs(int x, int y){
queue< pair<int,int> > q; // 이용할 큐, (x,y) -> (행, 열)
q.push(make_pair(x,y)); // pair를 만들어서 queue에 넣습니다.
// 처음 x,y를 방문 했기때문에
visited[x][y] = true;
groups[group_id]++;
while(!q.empty()){
// 큐의 현재 원소를 꺼내기
x = q.front().first;
y = q.front().second;
q.pop();
// 해당 위치의 주변을 확인
for(int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
// 지도를 벗어나지 않고
if(0 <= nx && nx < n && 0 <= ny && ny < n){
// 집이면서 방문하지 않았다면 -> 방문
if(map[nx][ny] == 1 && visited[nx][ny] == false){
visited[nx][ny]=true;
// 해당 단지의 집의 수를 증가시킴
groups[group_id]++;
// 큐에 현재 nx,ny를 추가
q.push(make_pair(nx,ny));
}
}
}
}
}
int main (){
scanf("%d", &n);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++)
//입력을 1개씩 숫자로 끊어서 받습니다 -> %1d
scanf("%1d", &map[i][j]);
}
// 전체 지도 탐색
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
// 집이면서 방문하지 않았다면 -> 방문
if(map[i][j]==1 && visited[i][j]==false){
// 해당 지역에 단지 id를 부여하고
group_id++;
// 탐색
//dfs_recursion(i, j);
//dfs_stack(i, j);
//bfs(i, j);
}
}
}
// 단지마다 집들의 수로 오름차순 정렬
// ID는 1부터 시작
// 함수 사용법: https://twpower.github.io/71-use-sort-and-stable_sort-in-cpp
sort(groups + 1, groups + group_id + 1);
printf("%d\n", group_id);
for (int i = 1; i <= group_id; i++) {
printf("%d\n", groups[i]);
}
}
