[ C++ ] #2178 미로탐색

미로찾기는 BFS에서 많이 나오는 문제이다. 

 

미로찾기 까지는 성공했지만,,, 이 문제의 핵심인 최단경로구하는거에서 막혔다..

가다가 이길이 아닐때 어떻게 거리를 구하지...???

 

맞는일인지 아닌지 어떻게 알고 거리를 update하지??

 

이 것에 대한 해결방안으로 방문했는지 체크하는 배열에 이 자리까지 오는데 걸린 거리를 저장하는걸로 하였다.

다이나믹 프로그래밍..을 이용했다고 볼 수 있을 것 같다. 

 

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


using namespace std;

int check[100][100];
int n, m;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
string a[100];

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++)
		cin >> a[i];

	queue<pair<int, int>> Q;
	Q.push({ 0,0 });
	check[0][0] = 1;


	while (!Q.empty()) {
		auto C = Q.front();

		Q.pop();
	

		for (int i = 0; i < 4; i++) {
			int nx = C.first + dx[i];
			int ny = C.second + dy[i];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
				continue;
			}
			if (a[nx][ny] == '0' || check[nx][ny] >= 1) {
				continue;
			}

			check[nx][ny] = check[C.first][C.second] + 1;
			Q.push({ nx,ny });

		}
	}

	cout << check[n - 1][m - 1];
}