[PS][완전탐색][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++;
	}
}