[210327][백준/BOJ] 2178번 미로 탐색

문제

입출력

---

풀이

배열의 왼쪽 상단부터 오른쪽 하단까지의 거리를 구하는 문제이며 한개의 시작지점을 가진 BFS 문제이다.

1. 문자열 형식으로 배열을 받는것을 생각하고 문제를 풀어야 한다.
2. 미로를 의미하는 board는 char형이나 string형으로, 각 위치로부터 시작지점까지의 거리를 구하기 위한 dist 배열은 int형으로 정의
3. dist 배열은 -1로 초기화
4. dist값이 0보다 작거나(방문 한적이 없음) board값이 '0'(길이 아님)이라면 continue
5. 다음 원소의 dist 값은 현재 원소의 dist 값 + 1
   
6. 문제의 특성상 + 1을 해줘야 답이 된다.

코드

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define SIZE 102

char board[SIZE][SIZE];
int dist[SIZE][SIZE];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main()
{
	int n, m;
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

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

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

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

	while (!Q.empty())
	{
		auto cur = Q.front(); Q.pop();
		for (int dir = 0; dir < 4; ++dir)
		{
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (dist[nx][ny] >= 0 || board[nx][ny] == '0') continue;
			dist[nx][ny] = dist[cur.X][cur.Y] + 1; // 다음 원소의 dist 값은 현재 원소의 dist + 1
			Q.push({ nx,ny });
		}
	}
	cout << dist[n - 1][m - 1] + 1;
}