[백준 2178/c++] 미로 탐색

BFS 를 이용한 문제

거리를 문제에서 물었으므로, 각 좌표까지의 거리를 담을 2차원 배열 dist를 만들고 fill 로 -1을 채워넣는다

이전의 그림 문제처럼 상하좌우를 flood fill 방식으로 채워 나가되, visited 의 방문 여부 대신에

dist의 해당 좌표 값이 0보다 작거나 (방문전이라 거리 값을 넣기전이니 기본 값 -1을 가짐)

board 좌표 값이 1이 아닌지 (1이어야만 지날 수 있으므로)를 판단하여 새로 이동할 dist의 좌표 값에 +1 을 해준다

그리고 이동할 새 좌표값을 큐에 넣어주어 큐가 빌때까지(더 갈 곳이 없을때까지) 수행 후

dist 의 목표 좌표값 (n, m) 을 출력하면 된다.

단, 1,1 에서 시작한다고 하였으니 1,1 위치를 왼,위로 하나씩 움직여 탐색 시작인 0, 0 으로 만들어 주기 위해서

dist[n-1][m-1] 로 만들고,  시작 부분의 위치도 1로 한다 하였으니 +1 을 해주어 좌표의 위치값을 구하는 문제이다

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

2178번: 미로 탐색

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

int n, m;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int dist[104][104];
string board[104];

int main(){
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> board[i];
	}
	for (int i = 0; i < n; i++)
	{
		fill(dist[i], dist[i] + m, -1);
	}
	queue<pair<int, int>> Q;
	Q.push({0, 0});
	dist[0][0] = 0;
	while (!Q.empty())
	{
		auto current = Q.front();
		Q.pop();
		for (int direction = 0; direction <4; direction++)
		{
			int nx = current.first + dx[direction];
			int ny = current.second + dy[direction];
			if (nx < 0 || nx >= n || ny < 0 || ny >=m)
			{
				continue;
			}
			if (board[nx][ny] != '1' || dist[nx][ny] >= 0)
			{
				continue;
			}
			dist[nx][ny] = dist[current.first][current.second] + 1;
			Q.push({nx, ny});
		}
	}
	cout << dist[n - 1][m - 1] + 1;
	return 0;
}