2178. 미로 탐색 (C++)

개인적으로는 이 문제가 그림 문제보다 쉬웠다. 

미로의 최소칸 수를 구하는 문제다. BFS를 이용하여 지나간 곳이 아니거나 0이 아닌곳만 열심히 이동하다보면 나오는 문제다.

 

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

string board[102];
int dist[102][102];
int n,m;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		cin >> board[i];
	}
	
	for(int i = 0; i < n; i++) fill(dist[i], dist[i]+m, -1);
	
	queue<pair<int,int>> Q;
	Q.push({0,0});
	dist[0][0] = 0;
	
	while(!Q.empty()) {
		auto cur = Q.front(); Q.pop();
		for(int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if(dist[nx][ny] >= 0 || board[nx][ny] != '1') continue;
			dist[nx][ny] = dist[cur.X][cur.Y]+1;
			Q.push({nx,ny});
		}
	}
	cout << dist[n-1][m-1]+1 << endl;
}

그림문제와 똑같은 구조지만, 여기는 약간 다른점이 1을 찾아서 개수까지 카운트 하거나, 뭐 그런거 없이 그냥 수만 세면 되는 문제라 간단하다. 그리고 문제 구조상 출력될때의 값에 +1을 해줘야 한다.(고 강의에서 그랬다)

또 다른점이라면, 미로를 string 으로 받았고, bool 형식의 배열이 아닌 int 형의 dist배열로 변경했다는 점이다.

이 문제는 true, false로 간단하게 맞고 틀리고를 세는게 아닌, 지나가면서 지나간 번수를 세야 미로의 최소칸을 구할 수 있기때문에 int 형으로 선언하여 수를 얻게 했다.(라고 강의에서 그랬다)(근데 이렇게 하면 ㄹㅇ 편하다)

while문 도는건 저번거와 똑같기에 패쓰으..