[BOJ 백준] 2178번 미로 탐색 / C++

문제

---

문제를 보시려면 링크를 클릭해주세요.

풀이

---

BFS(너비 우선 탐색)로 풀었습니다.

미로에 해당하는 수들이 붙어서 입력되므로 string 배열로 받았습니다.

미로를 지날 때, 방문한 적이 없고 이동할 수 있는 칸을 찾아 상,하,좌,우로 이전 큐의 이동거리 + 1 만큼 dist 배열에 담아줍니다.

소스 코드

---

#include <iostream>
#include <utility>
#include <string>
#include <queue>

using namespace std;

int main(){
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	string arr[101]; // 미로
	int dist[101][101]; // 이동 거리
	bool chk[101][101]; // 방문 체크
	
	queue<pair<int,int> > Q;
	int n,m;

	cin >> n >> m;
	
	int dx[4] = {1,0,-1,0};
	int dy[4] = {0,1,0,-1};
	
	for(int i=0; i<n; i++){
		cin >> arr[i];	
	}
	
	dist[0][0] = 1;
	Q.push({0,0});
	chk[0][0] = 1;
	
	while(!Q.empty()){
		
		pair<int,int> cur = Q.front();
		Q.pop();
		
		for(int dir=0; dir<4; dir++){ 
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			
			if(nx < 0 || nx >= n || ny < 0 || ny >=m)
				continue;
				
			if(arr[nx][ny]=='0' || chk[nx][ny])
				continue;
			
			dist[nx][ny] = dist[cur.first][cur.second] + 1;
			Q.push({nx,ny});
			chk[nx][ny] = 1;
			
		}
	}

	cout << dist[n-1][m-1];
	
	return 0; 

}