백준 2178번 미로 탐색 C++ 풀이

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

2178번: 미로 탐색

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.

 

bfs를 이용하여 왼쪽 위에서 오른쪽 아래까지 이동하기 위해 필요한 이동의 개수를 측정하는 문제이다.

 

문제의 포인트

bfs를 떠올릴 수 있고, 구현할 수 있는가?

코드

#include<iostream>
#include<queue>
#include<string>
#include<vector>
using namespace std;
const int MAX = 100;

int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 }; //탐색용
int n, m, a[MAX][MAX], visited[MAX][MAX], y, x;
int main() {
	cin >> n >> m;
	string temp;
	for (int i = 0; i < n; i++) 
	{
		cin >> temp;
		for (int j = 0; j < m; j++) 
		{
			a[i][j] = temp[j] - '0';
		}
			temp = "";
	}
	queue<pair<int, int>> q;
	visited[0][0] = 1;
	q.push({ 0, 0 });
	while (q.size()) 
	{
		y = q.front().first;
		x = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 0 || ny >= n|| nx < 0 || nx >= m) continue;
			if (a[ny][nx] == 0) continue;
			if (visited[ny][nx] != 0) continue;

			visited[ny][nx] = visited[y][x] + 1;
			q.push({ ny, nx });
		}
	}
	cout << visited[n - 1][m - 1];
	return 0;
}

여담

범위계산 때문에 여러 번 틀렸다.. 범위 계산을 하는 것이 중요함을 다시금 상기했다.