BFS 백준-2178 미로탐색 (실버 1)

해당 문제는 BFS를 사용하여서 문제를 풀 수 있습니다.

 

BFS로 0,0부터 시작해서 vis[0][0]에 1을 넣고 시작합니다.

 

그리고 continue 조건에서 1보다 클 때만 continue 시키도록 합니다 그 이유는 nx,ny값에
움직이기 전의 값인 cur.first, cur.second의 값의 +1한 값을 넣어야 하는데 같은 높이에 위치하는 노드 중 어떠한 한 노드가 먼저 방문을 했다면 최단거리를 구하기 위해 continue를 시켜 +1를 하지 않게 해야 합니다

 

그럼 while문이 끝나고 Q가 비었을때 vis[n-1][m-1]을 출력한다면 미로의 최단거리가 나옵니다.

 

#include <iostream>
#include <queue>


using namespace std;

int board[101][101] = {0,};
int vis[101][101] = {0,};
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};





int main(){
	
	int n, m;
	
	cin >> n >> m;

	char c;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> c;
			
			if(c == '0'){
				board[i][j] = 0;
			}
			else{
				 board[i][j] = 1;
			}
		}
	}
	
	queue<pair<int,int> > Q;
	
	Q.push({0,0});
	vis[0][0] = 1;
	
	while(!Q.empty()){
		pair<int,int> cur = Q.front(); Q.pop();
		
		for(int k = 0; k < 4; k++){
			int nx = cur.first + dx[k];
			int ny = cur.second + dy[k];
			
			if((nx < 0 || nx >= n) || (ny < 0 || ny >= m)) continue; 
			if((board[nx][ny] == 0) || (vis[nx][ny] > 1)) continue;
			 
			Q.push({nx,ny});
			vis[nx][ny] += vis[cur.first][cur.second]+1;
		}
	}
	
	cout << vis[n-1][m-1];
}