[이론][완전탐색][BFS] Chapter 0

완전탐색의 세 번째 알고리즘 BFS 문제를 풀어보겠습니다.

---

BFS는 개념은 생략하고 코드에서의 스킬을 학습하겠습니다.

BFS : 문제

BFS는 바로 간단한 문제로 접근하겠습니다.

2차원 BFS : 기본 코드

미로 탐색

문제의 정답은 여기에서 확인할 수 있습니다.

2차원 BFS : 가지 치기

미로탐색 문제는 2차원 BFS의 기본 조건만 가지고 있는 문제라서 위 정답 코드를 기반으로 설명하겠습니다. 이 문제는 (0,0)에서 (n-1,m-1)로 가는 것이 정해져 있기 때문에 “만약 (0,0)에서 시작해서 (n-1,m-1)로 갈 수 없는 경우 -1을 출력하시오”라는 조건이 있을 때는 접근 방법이 여러 개 있습니다.

1. bool flag=false 정의 후, curr.first == n-1 && curr.second == m-1 일 때, flag = true;
2. bfs() 모두 끝나고 dist[n-1][m-1] == 0 이면 cout« -1
3. 아래 코드에서 명시한 위치에 cout« -1;

3번 째 방법의 경우 while이 끝나는 것은 bfs의 핵심 알고리즘이 다 끝나는 것이기 때문에 if(curr.first == n-1 && curr.second == m-1){return;}에 의해서 return이 되지 않았다면 (n-1,m-1)로 가는 경우가 없다는 의미가 됩니다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int n=0, m=0;
int map[100][100];
int dist[100][100];
bool visited[100][100];
queue<pair<int, int> > q;
int dx[4] ={0,0,1,-1};
int dy[4] ={1,-1,0,0};
void bfs(int x, int y){
    dist[x][y]= 1;
    visited[x][y] = true;
    q.push(make_pair(x,y));
    while(!q.empty()){
        pair<int, int> curr = q.front();
        q.pop();
    //if(curr.first == n-1 && curr.second == m-1){
    //  return;
    //}
        for(int k=0; k<4; k++){
            int nx = curr.first + dx[k];
            int ny = curr.second + dy[k];
            if(nx<0 || nx>=n) continue;
            if(ny<0 || ny>=m) continue;
            if(!map[nx][ny]) continue;
            if(visited[nx][ny]) continue;
            q.push(make_pair(nx,ny));
            dist[nx][ny] = dist[curr.first][curr.second] + 1;
            visited[nx][ny] = true;
        }
    }
  //cout<< -1; 3번 째 방법
}

int main (void){
    cin>> n>> m;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            scanf("%1d", &map[i][j]);
        }
    }

    bfs(0,0);
    // for(int i=0; i<n; i++){
    // 	for(int j=0; j<m; j++){
    // 		cout<< dist[i][j]<<" ";
    // 	}
    // 	cout<<"\n";
    // }
    cout<<dist[n-1][m-1];
    return 0;
}

2차원 BFS : 한 층씩 순회하기

그래프의 높이를 계산하는 방법

1. visted[100][100]를 int type으로 정의해서 아래 코드의 dist[100][100]를 대신하기
2. while(size–)를 사용해서 그래프의 한 층이 끝날 때마다 체크하기

int n=0, m=0;
int map[100][100];
int dist[100][100];
bool visited[100][100];
queue<pair<int, int> > q;
int dx[4] ={0,0,1,-1};
int dy[4] ={1,-1,0,0};
void bfs(int x, int y){
    dist[x][y]= 1;
    visited[x][y] = true;
    q.push(make_pair(x,y));
    while(!q.empty()){
        int size = q.size();
        while(size--){
            pair<int, int> curr = q.front();
            q.pop();
            for(int k=0; k<4; k++){
                int nx = curr.first + dx[k];
                int ny = curr.second + dy[k];
                if(nx<0 || nx>=n) continue;
                if(ny<0 || ny>=m) continue;
                if(!map[nx][ny]) continue;
                if(visited[nx][ny]) continue;
                q.push(make_pair(nx,ny));
                dist[nx][ny] = dist[curr.first][curr.second] + 1;
                visited[nx][ny] = true;
            }
        }
        //그래프 한 층 추가
        height++;
    }
}