[백준] [C/C++] [★] 2206번 : 벽 부수고 이동하기

✅ 문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

✅ 입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

✅ 출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

✅ 예제 입력 1

6 4
0100
1110
1000
0000
0111
0000

✅ 예제 출력 1

15

✅ 예제 입력 2

4 4
0111
1111
1111
1110

✅ 예제 출력 2

-1

✅ 알고리즘 [ 접근 방법 ]

어렵다 어려워.. 도저히 모르겠어서 레퍼런스를 찾아보고 풀었다.. 좀더 실력을 키워야 풀 수 있을 것 같다. 일단 BFS로 접근해야 할 것은 분명했다. 다만 벽을 뚫는 경우와 안뚫는 경우를 나눠줄 필요가 있었기에 이를 처리하기 위한 새로운 방법이 필요했다.

풀이하면서 몰랐던 요소를 몇가지 먼저 기록해두겠다.

1. 이중 pair 문법
2. 테스트케이스 배열에 띄어쓰기가 없는 경우

1. 벽을 뚫는 경우와 안뚫는 경우를 구분짓기 위해 3중배열을 사용했는데 이를 queue에 넣기위해서는 pair를 두번 써야만 했다. 근데 정확한 문법이 헷갈려서 좀 헤맸다. 이중 pair를 쓸때는 다음과 같은 문법으로 쓰자!

queue <pair<pair<자료형,자료형>,자료형>

1. 이건 제발좀 기억하자. 테스트 케이스 배열에 띄어쓰기 없이 입력되어 있는 경우 cin » 으로 받으면 오류가 생긴다. 반드시 scanf를 사용하여 입력받자!!

나머지는 일반적인 BFS 풀이 방식으로 풀어주면 된다.. 아직 멀었다 더 연습하자

✅ 풀이

#include <iostream>
#include <queue>

using namespace std;

int n, m;
int arr[1001][1001];
int visit[1001][1001][2]; // 최단거리값
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };

int bfs() {
	queue <pair<pair<int, int>, int>> q; // x좌표, y좌표, 벽뚫 유무
	q.push({ { 1,1 }, 0 });
	visit[1][1][0] = 1;
	while (!q.empty()) {
		int x = q.front().first.first;
		int y = q.front().first.second;
		int wall = q.front().second;
		q.pop();

		if (x == n && y == m) return visit[x][y][wall];

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 1 && nx <= n && ny >= 1 && ny <= m) {
				// 벽이 없고 아직 방문하지 않은 경우
				if (arr[nx][ny] == 0 && visit[nx][ny][wall] == 0) {
					visit[nx][ny][wall] = visit[x][y][wall] + 1;
					q.push({ { nx,ny }, wall });
				}

				// 벽이 있고 아직 벽을 뚫지 않은 경우
				if (arr[nx][ny] == 1 && wall == 0) {
					visit[nx][ny][wall + 1] = visit[x][y][wall] + 1;
					q.push({ {nx,ny}, wall + 1 });
				}
			}
		}
	}
	return -1;
}

int main() {

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%1d", &arr[i][j]);
		}
	}

	cout << bfs() << endl;
}