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

간단한 BFS 문제이다.

경로는 대부분 BFS를 돌리면 찾을 수 있으므로 BFS로 접근해서 풀었다

처음에는 변수를 올리면서 탐색을 했는데,

이렇게 하면 BFS를 다 돈 값이 나와서 어떻게 하나 고민을 했었는데,

그냥 다른 이차원 배열에 경로를 이동한 값을 넣어주면서 다니면 되는걸 깨달았다.

 

#include <iostream>
#include <string>
#include <queue>
#include <vector>
using namespace std;

int n, m;

char maze[100][100];
int cnt[101][101];
bool visited[100][100];

const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, 1, -1 };


int main() {

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

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> maze[i][j];
		}
	}

	queue<pair<int, int>> q;
	q.push({ 0, 0 });
	visited[0][0] = true;
	cnt[0][0] = 1;
	while (!q.empty()) {
		auto current = q.front();
		q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int nx = current.first + dx[dir];
			int ny = current.second + dy[dir];

			if (nx < 0 || ny < 0 || nx >= n || ny >= m)
				continue;
			if (visited[nx][ny] == true) 
				continue;
			if (maze[nx][ny] == '1' && visited[nx][ny] == false) {
				visited[nx][ny] = true;
				q.push({ nx, ny });
				cnt[nx][ny] = cnt[current.first][current.second] + 1;
			}
		}
	}

	cout << cnt[n - 1][m - 1] << '\n';

	return 0;

}