[이것이 코딩테스트다]미로 탈출(C++)

https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=247882118

이것이 취업을 위한 코딩 테스트다 with 파이썬

해당 도서의 DFS/BFS 단원의 실전문제 4번 '미로 탈출'을 풀이한다.

---

01. 이 문제는 DFS가 아니라 왜 BFS로 풀었을까?

시작지점에서 가장 가까운 노드부터 탐색하므로, 최종 도착지까지 가장 가까운 노드만을 타고 들어가게 된다.

따라서 결과에 최단거리가 나오게 된다.

---

02. 풀이

문제 조건

• 괴물이 있는 곳은 0, 없는 곳은 1이다.
• 동빈이의 위치는 (1,1) 이고 미로의 출구는 (N,M)이다.
• 동빈이가 움직여야 하는 최소의 칸 개수를 구하세요.

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

int N, M;
int** map;
queue<pair<int, int>> q;

int direction[4][2] = {
	{-1,0},
	{1,0},
	{0,-1},
	{0,1}
};

void input() {
	scanf("%d %d", &N, &M);
	map = new int* [N];
	for (int i = 0; i < N; i++) map[i] = new int[M];

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) scanf("%d", &map[i][j]);
	}
}

void solution() {
	q.push(make_pair(0, 0));

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int dx = x + direction[i][0];
			int dy = y + direction[i][1];

			if (dx < 0 || dx >= N || dy < 0 || dy >= M) continue;
			if (map[dx][dy] == 0) continue;
			if (map[dx][dy] == 1) {
				map[dx][dy] = map[x][y] + 1;
				q.push(make_pair(dx, dy));
			}
		}
	}

	printf("%d", map[N - 1][M - 1]);
}

int main(void) {
	input();
	solution();
}

도출 방법

-> BFS로 주변 칸을 탐색하면서, 갈 수 있는 곳이면 현재 위치의 숫자에 1을 더해준다.

-> 갔을 경우 pop, 가지 못하는 곳은 처음부터 큐에 넣지 않는다.