백준 2178 _ 미로 탐색

www.acmicpc.net/problem/2178

2178번: 미로 탐색

---

✨ 내 소스 코드

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

int N, M;
int MAP[101][101];
string temp;
int Route[4][2] = { {0,-1},{1,0},{0,1},{-1,0} };

void bfs() {
	queue<pair<int,int>> q;
	q.push(make_pair(0, 0));
	int nx, ny;
	pair<int, int> current;

	while (!q.empty()) {
		current = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			nx = current.first + Route[i][0];
			ny = current.second + Route[i][1];
			if (0 <= nx && nx < N && 0 <= ny && ny < M && MAP[nx][ny]==1) {
				q.push(make_pair(nx, ny));
				MAP[nx][ny] = MAP[current.first][current.second] + 1;
			}
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> N >> M;
	for (int i = 0; i < N;i++) {
		cin >> temp;
		for (int j = 0; j < M; j++) {
			MAP[i][j] = temp[j]-'0';
		}
	}

	bfs();
	cout << MAP[N - 1][M - 1];
	return 0;
}

 

🙏 문제 풀이

미로를 탐색하는 것은 BFS를 이용하여 어려움 없이 풀었지만

이동한 칸 수를 구하는 데에서 골머리를 앓았다

결국 DP를 살짝 섞는 걸로 해결하였다

 

위와 같은 방식으로 이동한 칸 수를 구하게 된다

 

⭐ 문제 풀이 결과