[백준2178] 미로 탐색 (C++)

📌 문제

BOJ 바로가기

대표적인 BFS 문제이다. 출발점부터 목적지까지의 최단경로를 구해야 한다.

🗡 풀이

📌 ans 배열에 (x,y)까지의 최단거리를 저장해주었고, (x, y)에서 (nx, ny)로 넘어갈 때마다 ans[nx][ny]에 ans[x][y]+1 값을 넣어주었다.

if (1 <= nx && nx <= n && 1 <= ny && ny <= m
	&& !visited[nx][ny] && map[nx][ny] == 1)
	{
		q.push({ nx, ny });
		visited[nx][ny] = true;
        ans[nx][ny] = ans[x][y] + 1; ✨
		if (nx == n && ny == m)
			return;
	}

📌 dx, dy 배열을 선언해서 현위치로부터 상하좌우의 위치를 한번에 push할 수 있도록 만들어주었다.

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

📌 전체 소스코드는 다음과 같다.

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

int n, m, map[101][101], ans[101][101];
bool visited[101][101] = { false };
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

void bfs(int x, int y)
{
	queue<pair<int, int>> q;
	q.push({ x, y });
	visited[x][y] = true;
	ans[x][y] = 1;
	while (!q.empty())
	{
		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 (1 <= nx && nx <= n && 1 <= ny && ny <= m
				&& !visited[nx][ny] && map[nx][ny] == 1)
			{
				q.push({ nx, ny });
				visited[nx][ny] = true;
				ans[nx][ny] = ans[x][y] + 1;
				if (nx == n && ny == m)
					return;
			}
		}
	}
}

int main()
{
	cout.tie(nullptr);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			scanf("%1d", &map[i][j]);
		}
	}
	bfs(1, 1);
	cout << ans[n][m];
}