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

문제

N×M크기의 배열로 표현되는 미로가 있다.
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

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

출력

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

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

풀이

최단거리문제는 대부분 BFS로 접근한다.
인접칸으로의 이동은 상하좌우로만 가능하고, 이동간의 모든 비용은 1로 동일하다. 사용된 변수는 아래와같다.

• int map[][] : 입력받은 지도 정보
• int res[][] : 해당 칸까지의 최소 이동 비용
• bool visited[][] : 해당칸을 방문했는지 check
• dx[4], dy[4] : 상하좌우 이동만이가능하므로, 이때 필요한 방향벡터.

시작위치는 좌상단인 0,0 부터 이 위치부터 이동한위치마다 인접한 4방향칸이 유효하면 큐에 넣어서 큐가 빌때까지 모든 칸의 이동비용을 res변수에 담는다.
마지막에 맨처음에 이동하는 비용으로 +1을 해주고 출력하면 끝이다.

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using std::queue; using std::pair;
int n, m, ** map, ** res;
bool** visited;
int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { -1, 0, 1, 0 };

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

	while (!q.empty()) {
		x = q.front().first;
		y = q.front().second;

		q.pop();
		
		//4방향으로 이동
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];

			if (0 <= xx && xx <= n - 1 && 0 <= yy && yy <= m - 1) {
				if (map[xx][yy] == 1 && !visited[xx][yy]) {
					visited[xx][yy] = true; //방문했음
					res[xx][yy] = res[x][y] + 1; //x, y에서 이동거리 +1
					q.push({ xx, yy }); //이동한위치 에서 다시 탐색하도록
				}
			}
		}
	}
}

int main(void) {
	scanf("%d%d", &n, &m);
	map = new int* [n];
	res = new int* [n];
	visited = new bool* [n];
	for (int i = 0; i < n; i++) {
		map[i] = new int[m];
		res[i] = new int[m];
		visited[i] = new bool[m];
		char c;
		scanf("%c", &c); //줄바꿈문자지움
		for (int j = 0; j < m; j++) {
			scanf("%c", &c);
			if (c == '1')
				map[i][j] = 1;
			else
				map[i][j] = 0;
			res[i][j] = 0;
			visited[i][j] = false;
		}
	}

	BFS(0, 0); //0, 0부터 탐색시작

	printf("%d\n", res[n - 1][m - 1] + 1);

	return 0;
}