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

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

2206번: 벽 부수고 이동하기

백준 2206번 벽 부수고 이동하기를 풀어봤습니다.

기존 BFS문제에 벽을 부술 수 있는 상태가 추가됐습니다. 

처음엔 벽을 부수고 이동하는 것과 안부수고 이동하는 것에 차이를 안두고 풀었더니 문제가 생겼습니다. 그래서 이동 거리를 저장하는 check배열과 방문한 적 있는지 확인하는 visited배열에도 상태를 추가해서 3차원 배열로 만들었습니다.

벽을 부술 수 있으면 1, 없으면 0으로 가정하고 풀었습니다.

 

움직일 좌표가 범위 안에 있는지 체크하는 것 까지 동일합니다. 

그 후에 4가지 경우의 수가 생깁니다.

1. 만약 다음 좌표가 벽이고 부술 수 있다면 다음 좌표와 0을 큐에 넣습니다.

2. 만약 다음 좌표가 벽이고 부술 수 없다면 아무것도 하지 않습니다.

3. 만약 다음 좌표가 벽이 아니고 방문한 적이 없다면 다음 좌표와 현재 상태를 큐에 넣습니다.

4. 만약 다음 좌표가 벽이 아니고 방문한 적이 있다면 아무것도 하지 않습니다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
using namespace std;

int n, m;
int N, M;
int map[1000][1000];
bool visited[2][1000][1000];
int check[2][1000][1000];

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

queue<pair<pair<int, int>, int>> q;

void BFS() {
	while (!q.empty()) {
		int x = q.front().first.first;
		int y = q.front().first.second;
		int numDestroy = q.front().second;
		visited[numDestroy][x][y] = 1;
		q.pop();

		if (x == N && y == M) {
			cout << check[numDestroy][x][y] + 1;
			return;
		}

		for (int i = 0; i < 4; i++) {
			int next_x = x + dx[i];
			int next_y = y + dy[i];

			if (next_x >= 0 && next_x < n
				&& next_y >= 0 && next_y < m) {
				// If next step is wall and can destroy wall
				if (map[next_x][next_y] == 1 && numDestroy) {
					q.push({ {next_x,next_y},0 });
					check[numDestroy-1][next_x][next_y] = check[numDestroy][x][y] + 1;
					visited[numDestroy-1][next_x][next_y] = 1;
				}
				// If next step is not wall and didn't visit
				else if (map[next_x][next_y] == 0 && visited[numDestroy][next_x][next_y]==0) {
					q.push({ {next_x,next_y},numDestroy });
					check[numDestroy][next_x][next_y] = check[numDestroy][x][y] + 1;
					visited[numDestroy][next_x][next_y] = 1;
				}
			}
		}
	}


	cout << -1;
}
int main() {
	cin >> n>> m;
	N = n - 1;
	M = m - 1;
	string str;
	for (int i = 0; i < n; i++) {
		cin >> str;
		for (int j = 0; j < m; j++) {
			if (str[j] == '1') {
				map[i][j] = 1;
			}
		}
	}


	q.push(make_pair(make_pair(0, 0), 1));
	BFS();


	return 0;
}