[C++][백준] - 미로 탐색 (2178번)

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

2178번: 미로 탐색

🔔 문제 : 

(2<= N,M <= 100)인 N*M 크기의 배열로 표현되는 미로가 있습니다.

1은 이동할 수 있는 칸이고, 0은 이동할 수 없는 칸입니다.

 

왼쪽상위 (1,1) 부터, 오른쪽하위인 (N,M)까지 가는 최단거리 길을 찾아서, 그 칸수를 출력하면 되는 문제입니다.

---

🔔 Kick Point :

BFS로 길을 찾으면서, 그 길의 칸마다 몇번째 칸인지를 넣어 최솟값을 찾았습니다.

 

지도를 map[102][102]로 102로 준 까닭은, 바깥쪽은, 0으로 패딩을 주기 위해서 하였습니다.

 

queue에는 pair( pair(좌표) , 현재 지나간 칸수) 를 두어서, 쉽게쉽게 칸수까지 구하였습니다.

 

---

🔔 Code :

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

int n, m;
bool map[102][102] = { {0,} };
queue<pair<pair<int,int>,int>> q;

void BFS() {

	q.push({ {1,1},1 });
	map[1][1] = false;

	int MIN = 10001;
	while (!q.empty()) {
		int _x = q.front().first.first;
		int _y = q.front().first.second;
		int cnt = q.front().second;

		if (_x == n && _y == m) {
			MIN = MIN > cnt ? cnt : MIN;
		}

		q.pop();

		if (map[_x+1][_y]) {
			q.push({ {_x+1, _y}, cnt +1 });
			map[_x+1][_y] = false;
		}
		if (map[_x][_y+1]) {
			q.push({{ _x, _y + 1}, cnt + 1});
			map[_x][_y+1] = false;
		}
		if (map[_x -1][_y]) {
			q.push({ { _x - 1, _y }, cnt + 1 });
			map[_x-1][_y] = false;
		}
		if (map[_x][_y-1]) {
			q.push({ { _x, _y -1 }, cnt + 1 });
			map[_x][_y-1] = false;
		}
	}

	cout << MIN;
}


int main() {
	
	// INPUT (n,m)
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char tmp;
			cin >> tmp;
			if(tmp == '1') map[i][j] = true;
			else map[i][j] = false;
		}
	}
	// Algorithm
	BFS();

}

---