🙄미로탈출(최단거리)

https://www.acmicpc.net/problem/2178
문제설명
N by M 크기의 직사각형 형태의 미로에 갇혀있다. 미로에는 괴물이 있어 이를 피해서 탈출해야 한다. 유저의 초기 위치는 (1, 1)이고 미로의 출구는 (N, M) 위치에 존재하며 한 번에 한 칸 씩 이동이 가능하다. 이 때 괴물이 있는 부분은 0, 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이 때 유저가 미로를 탈출하기 위해 움직여야 할 최소 칸의 개수를 구해라. 단, 칸을 셀 때 시작, 마지막 칸도 포함시켜야 한다.

입력조건

첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

출력조건

첫째 줄에 최소 이동 칸의 개수를 출력한다.

입력 예시

5 6
101010
111111
000001
111111
111111

출력 예시

10

😏 구현

#include <bits/stdc++.h>

using namespace std;

int graph[201][201];
int n, m;
int dx[]{-1,1,0,0};
int dy[]{0,0,-1,1};

int bfs(int x, int y)
{
	queue<pair<int, int>> q;
	q.push({ x,y });

	while (q.empty() == false)
	{
		 x = q.front().first;
		 y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (graph[nx][ny] == 0) continue;
			if (graph[nx][ny] == 1)
			{
				graph[nx][ny] = graph[x][y] + 1;
				q.push({ nx,ny });
			}
		}
	}
	return graph[n - 1][m - 1];
}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf_s("%1d", &graph[i][j]);

	cout << bfs(0, 0) << '\n';

	return 0;
}

2022.01.09 다시 구현

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

string graph[102];
int dist[102][102];

int dx[]{-1,1,0,0};
int dy[]{0,0,-1,1};

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

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> graph[i];

	for (int i = 0; i < n; i++)
		fill(dist[i], dist[i] + m, -1);

	dist[0][0] = 0;
	queue<pair<int, int>> Q;
	Q.push({ 0,0 });

	while (!Q.empty())
	{
		pair<int, int> cur = Q.front(); Q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = cur.X + dx[i];
			int ny = cur.Y + dy[i];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (dist[nx][ny] >= 0 || graph[nx][ny] != '1') continue;
			dist[nx][ny] = dist[cur.X][cur.Y] + 1;
			Q.push({ nx,ny });
		}
	}

	cout << dist[n - 1][m - 1] + 1 ;

	return 0;
}