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

문제 링크

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

 

문제 정보

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

풀이

 이 문제는 BFS의 응용 문제로 다차원 배열에서의 거리 측정 문제다!

 

소스 코드

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

#define X first
#define Y second

string board[102];
int dist[102][102]; // 거리를 저장할 배열
int n, m;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 }; 

int main(void) {
	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); // 거리를 저장할 배열을 미리 -1로 초기화해두면 vis 배열을 따로 둬서 방문 여부를 확인할 필요가 없다!
	}
	
	queue<pair<int, int>> Q;
	Q.push({0, 0});
	dist[0][0] = 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] != '1') {
				continue; // 거리를 저장한 배열을 -1로 초기화 해뒀으므로 만약 -1 보다 큰 값이 저장되어 있으면 이미 방문해서 거리를 잰 상태임!
			}
			
			dist[nx][ny] = dist[cur.X][cur.Y] + 1; // 거리는 1칸씩 늘어난다.
			Q.push({nx, ny});
		}
	}
	
	cout << dist[n - 1][m - 1] + 1; // 문제는 (1, 1)부터 시작한다고 했으므로 1칸을 더해줘야 한다!
	
	return 0;
}