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

풀이

#include <cstdio>
#include <queue>
using namespace std;

int N, M;
int a[101][101];
int ck[101][101];
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int main() {
	scanf("%d %d", &N, &M);
	for (int i=0; i<N; i++) {	// 입력
		for (int j=0; j<M; j++) {
			scanf("%1d", &a[i][j]);
			ck[i][j]=0;
		}
	}
	
	queue<pair<int,int>> q;
	q.push(make_pair(0,0));
	ck[0][0] = 1;
	while (!q.empty()) {
		int n = q.front().first;
		int m = q.front().second;
		q.pop();
		for (int k=0; k<4; k++) {	// 상하좌우 반복
			int nx = n + dx[k];
			int my = m + dy[k];
			if (0<=nx && nx<N && 0<=my && my<M) {
				if (a[nx][my]==1 && ck[nx][my]==0) {	// 갈 수 있는 곳이면
					q.push(make_pair(nx, my));	// q에 좌표 대입
					ck[nx][my] = ck[n][m]+1;	// ck 배열에 이전 값 + 1
				}
			}
		}
	}
	printf("%d", ck[N-1][M-1]);		// 목적지 ck 배열 값 출력
	return 0;
}

개념

미로 탐색도 종류가 다양하다.

이번 문제는 최소의 칸을 이동하여 목적지에 도달해야한다.

목적지에 도달만 하기 위해서라면 stack을 사용해도 상관이 없다.

하지만 최소의 칸을 이동해야하므로 dfs를 사용하면 각 탐색의 비교가 어려워진다.

bfs를 사용하면 노드로부터 넓게 뻗어져나가므로, 이동마다 비교가 용이하다. 

---

풀이

 

입력을 받고, ck 배열을 0으로 초기화 한다.

 

q에 0,0을 넣고, q가 빌 때까지 반복문에 넣는다.

q에 들어간 인자를 받아서 상하좌우에 대한 for문에 넣는다.

 

그 안에서 if문을 통해 q에 다음 값을 push한다.

여기서 중요한 부분은 ck[nx][my] = ck[n][m]+1; 이다.

 

그렇게 하면 다음과 같이, 단계마다 번호가 + 된다.