[백준 2178] 미로 탐색

풀이

N X M 크기의 맵에서 (1,1)에서 출발해서 (N,M)까지 도달하는데 걸리는 최소의 칸 수를 구하는 문제이다.

칸 과 칸 사이는 1이라는 비용으로 생각할 수 있다.

 

(1,1) -> (1,2) 로 가는 비용이 1이라는 뜻이다. 만약에 비용이 달랐다면 다른 방법으로 풀어야 한다.

비용이 모두 1로 같기 때문에 이 문제는 BFS 알고리즘으로 해결할 수 있다.

여기서는 (0,0) -> (N-1, M-1)로 구현했다.

 

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

int n, m;
int board[101][101];
bool vis[101][101];

int bfs()
{
	int dx[] = { 0,0,-1,1 };
	int dy[] = { 1,-1,0,0 };

	queue<pair<pair<int, int>, int> > q;
	q.push({ {0,0}, 1 });
	vis[0][0] = true;
	while (!q.empty())
	{
		int x = q.front().first.first;
		int y = q.front().first.second;
		int cnt = q.front().second;
		q.pop();

		if (x == n - 1 && y == m - 1)
			return cnt;

		for (int i = 0; i < 4; ++i)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			if (board[nx][ny] == 1 && !vis[nx][ny])
			{
				vis[nx][ny] = true;
				q.push({ {nx,ny}, cnt + 1 });
			}
		}
	}

	return -1;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		string str;
		cin >> str;
		for (int j = 0; j < str.length(); ++j)
		{
			board[i][j] = str[j] - '0';
		}
	}

	cout << bfs() << '\n';
	return 0;
}