백준 2178번: 미로 탐색 / bfs 구현

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int check[101][101];   //방문여부와 거리 합산하여 저장한다.
int grid[101][101];
int dx[4] = {-1,0,0,1 }; int dy[4] = { 0,-1,1,0 };
int n, m;

int bfs(int x, int y){
	queue<pair<int, int>> q;
	check[1][1] = 1; 
	q.push(make_pair(x, y));
	
	while (!q.empty()) {
		x = q.front().first; y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i]; int ny = y + dy[i];

			if (nx == n && ny == m) return check[x][y] + 1;

			if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && grid[nx][ny] == 1 && check[nx][ny] == 0) {
				q.push(make_pair(nx, ny));
				check[nx][ny] = check[x][y] + 1; // 거리 점화식
			}
		}
	}
}
int main() {
	//포인트: bfs로만 구현 가능하다.
	///미로 마지막 점까지 제일 빨리가는 경우의 수 구함.
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &grid[i][j]);
		}
	}
	cout<< bfs(1, 1)<<endl;

	return 0;
}