[Baekjoon] 2178번: 미로 탐색

🥅 문제

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

 

🔍 설계

미로가 주어지고, 1인 칸 중에서 인접한 칸으로 이동할 수 있다는 것에서 BFS라는 것을 파악했다.

 

지나야하는 최소 칸을 구해야 하기 때문에, 각 칸마다 그 칸으로 오기까지 이동한 총 칸의 수를 dp에 저장한다.

 

어떤 칸으로 이동했을 때, 이동하기 전 칸이 저장한 값+1이 이동한 칸까지 이동한 총 칸의 수이다. 이 값보다 이미 저장하고 있는 값이 작다면, 최소 칸을 구할 수 없으므로, 큐에 담지 않는다.

 

👊 풀이

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;	
int n, m;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
string temp;
vector<vector<int>> miro(100, vector<int>(100));
vector<vector<int>> dp(100, vector<int>(100, 1e9+7));
queue<pair<int, int>> q;

void bfs(){
	dp[0][0] = 1;
	q.push({0, 0});
	while (!q.empty()){
		int cur_x = q.front().first;
		int cur_y = q.front().second;
		q.pop();
		for (int i=0; i<4; i++){
			int new_x = cur_x + dx[i];
			int new_y = cur_y + dy[i];
			if (!(new_x >= 0 && new_x < n && new_y >=0 && new_y < m) || !miro[new_x][new_y]) {
				continue;
			}
			if (dp[new_x][new_y] > dp[cur_x][cur_y] + 1){
				q.push({new_x, new_y});
				dp[new_x][new_y] = dp[cur_x][cur_y] + 1;
			}
		}
	}
}

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i=0; i<n; i++){
		cin >> temp;
		for (int j=0; j<m; j++){
			miro[i][j] = temp[j] - '0';
		}
	}
	bfs();
	cout << dp[n-1][m-1] << "\n";
	return 0;
}

 

📝 메모

'1'-'0'으로 '1'을 1로 바꿀 수 있다.