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

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

#include<iostream>
#include<stdio.h>
#include<queue>
#include<vector>
#include<utility>
using namespace std;

int N, M;
int direct[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
vector<vector<int>> Map;


void BFS() {
	queue<pair<int, int>> Q;

	Q.push(make_pair(0, 0));

	while (!Q.empty()) {
		pair<int, int> know = Q.front();
		Q.pop();

		for (int i = 0; i < 4; i++) {
			int n = know.first + direct[i][0];
			int m = know.second + direct[i][1];

			if (0 <= n && n < N && 0 <= m && m < M && Map[n][m] == 1) {
				Q.push(make_pair(n, m));
				Map[n][m] = Map[know.first][know.second] + 1;
			}
		}

	}

}

int main(void) {
	cin >> N>> M;	//세로, 가로

	for (int i = 0; i < N; i++) {
		vector<int> tmap;
		for (int j = 0; j < M; j++) {
			int temp;
			scanf("%1d", &temp);
			tmap.push_back(temp);
		}
		Map.push_back(tmap);
	}

	BFS();

	cout << Map[N - 1][M - 1] << endl;
}