[백준] 2178번 미로 탐색

2178번: 미로 탐색

각 위치까지 가는데 얼마나 걸리는지 저장하다가 그 위치가 N-1, M-1일 때 출력시키면 된다.

 

0,0부터 시작하기 때문에 i,j에 0,0부터 넣어주고

상하좌우를 검사하며 maze의 값이 1이고 방문하지 않은 곳인 x, y을 찾은 뒤

i, j의 값+1을 넣고 방문에 체크해주고 x, y를 큐에 넣어준다.

이 과정이 끝나면 큐를 pop시켜주고 front에 있는 값을 i, j로 만든 다음 반복한다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;
int maze[101][101] = { 0 }, visited[101][101] = { 0 }, res[101][101] = { 0 };
int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 }; //상 하 좌 우 순
int x, y, a, b, c, d, finish = 0;
queue <pair<int, int>> q;
void Bfs(int N, int M) {
	int i = 0, j = 0;
	while (1) {
		for (int k = 0; k < 4; k++) {
			x = i + dx[k], y = j + dy[k];
			if (x >= 0 && x < N && y >= 0 && y < M && maze[x][y] == 1 && visited[x][y] == 0) {
				res[x][y] = res[i][j] + 1;
				visited[x][y] = 1;
				if (x == N - 1 && y == M - 1) {
					finish = 1;
					break;
				}
				q.push(pair<int, int>(x, y));
			}
		}
		if (finish) break;
		q.pop();
		i = q.front().first, j = q.front().second;
	}	
}

int main() {
	int N, M;
	cin >> N >> M;

	string input;
	for (int i = 0; i < N; i++) {
		cin >> input;
		for (int j = 0; j < input.size(); j++) {
			maze[i][j] = input[j] - '0';
		}
	}

	q.push(pair<int, int>(0, 0));
	res[0][0] = 1;
	visited[0][0] = 1;
	Bfs(N, M);
	cout << res[N - 1][M - 1];

	return 0;
}