[백준 2178] 미로 탐색 cpp

문제
NxM 크기의 배열로 표현되는 미로가 있다.
미로에서 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸이다.
이때 (1, 1)에서 출발하여 (N, M)으로 이동할 때 지나야 하는 최소의 칸 수를 구하라 한 칸에서 다른 칸으로 이동할 때는 서로 인접한 칸으로만 이동할 수 있다.
칸을 셀 때는 시작 위치와 도착 위치도 포함한다.

입력
첫째 줄에 두 정수 N, M을 입력한다. (2이상 100이하)
이후 정수의 정보를 입력한다.

출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다.

---

접근

출발점에서 도착점까지 최소길이로 가야한다. 그래서 이동할 때마다 카운트를해서 최솟값을 비교하는 방법을 생각해봤지만 BFS로 길을 탐색하다가 한 번 지나간길은 이전에 밟아온 칸에 +1을 해주어 최종적으로 도착점의 수를 출력하면 되겠다라는 생각을 하였다.

 

정리를 하면 BFS로 길을 탐색하고 현재 위치의 STEP + 1은 다음 위치의 STEP 수가 된다. 따라서 도착점에 저장된 수를 출력하면 된다.

 

구현

맵의 크기를 입력받고 맵에 대한 정보를 입력받는다. 이때 0과 1이 붙어서 들어오기 때문에 한 칸씩 map에 입력되도록 "%1d"를 사용햇다.

그리고 -1을 해주어 0이 길이되고 -1은 가지못하는 공간으로 표시하였다. 왜냐하면 방문표시를 1부터 할 것이기 때문이다.

cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &map[i][j]);
			map[i][j] -= 1;
		}
	}

 

그 다음 0, 0부터 BFS를 시작한다.

처음에 입력받은 0, 0에 1을 대입한다. 문제에서 출발점과 도착점도 칸 수에 포함시켜야 하기 때문이다.

이후 큐를 통해 BFS를 실행하며 다음 칸의 후보들에는 현재 칸에 저장된 수의 +1만큼 저장하여 방문표시도 하고 현재 위치까지의 거리도 표시하도록 한다.

void BFS(int y, int x) {
	map[y][x] = 1;
	queue<pair<int, int>> q;
	q.push({ y,x });

	while (!q.empty()) {
		int cy = q.front().first;
		int cx = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ny = cy + dir[d][0];
			int nx = cx + dir[d][1];
			if (RangeCheck(ny, nx) && map[ny][nx] == 0) {
				map[ny][nx] = map[cy][cx] + 1;
				q.push({ ny, nx });
			}
		}
	}
}

 

최종적으로 (N-1, M-1)의 값을 출력하면 해가 된다.

cout << map[N - 1][M - 1] << endl;

---

전체 코드

#include <iostream>
#include<algorithm>
#include <vector>
#include<queue>
#include<cstring>

using namespace std;

const int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
int N, M;
int map[100][100];


bool RangeCheck(int y, int x) {
	return(y >= 0 && y < N) && (x >= 0 && x < M);
}

void BFS(int y, int x) {
	map[y][x] = 1;
	queue<pair<int, int>> q;
	q.push({ y,x });

	while (!q.empty()) {
		int cy = q.front().first;
		int cx = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++) {
			int ny = cy + dir[d][0];
			int nx = cx + dir[d][1];
			if (RangeCheck(ny, nx) && map[ny][nx] == 0) {
				map[ny][nx] = map[cy][cx] + 1;
				q.push({ ny, nx });
			}
		}
	}
}
int main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &map[i][j]);
			map[i][j] -= 1;
		}
	}

	BFS(0, 0);

	cout << map[N - 1][M - 1] << endl;
	return 0;
}

/*
출발할 때 각 칸이 출발위치로부터 몇 칸 떨어져있는지 표시하기 (방문표시도 동시에 됨)
결국 끝에는 해가 담겨있음
그럼 BFS로 인접한 칸은 기준 점보다 1칸 증가

*/