[백준/BOJ] 2206번 벽 부수고 이동하기 (C++)

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

2206번: 벽 부수고 이동하기

벽 뚫기 사용의 유무를 체크하기 위해 3차원 배열을 이용해야 한다. 해당 아이디어만 잘 떠올린다면 어렵지 않게 해결할 수 있는 BFS 문제였다.

 

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

int N, M;
int map[1001][1001];
int visit[2][1001][1001];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

struct Pos {
	int x, y, flag; // flag - 0 : 벽 뚫기를 아직 사용 안함, 1: 벽 뚫기를 이미 사용함
};

int BFS() {
	queue<Pos> q;
	q.push({ 0, 0, 0 });
	visit[0][0][0] = 0;

	while(!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int flag = q.front().flag;
		q.pop();
		
		if(x == N - 1 && y == M - 1) return visit[flag][x][y] + 1;
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx >= 0 && nx < N && ny >= 0 && ny < M) {
                // 탐색하는 칸을 처음 방문하고, 벽이 없을 때
				if(visit[flag][nx][ny] == -1 && map[nx][ny] == 0) {
					q.push({ nx, ny, flag });
					visit[flag][nx][ny] = visit[flag][x][y] + 1;
                // 탐색하는 칸에 벽이 있고, 아직 벽 뚫기를 사용 안했을 때
				} else if(map[nx][ny] == 1 && flag == 0) {
					q.push({ nx, ny, 1 });
					visit[1][nx][ny] = visit[flag][x][y] + 1;
				}
			}
		}
	}
	
	return -1;
}

int main(void) {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> N >> M;
	for(int i = 0; i < N; i++) {
		string str;
		cin >> str;
		for(int j = 0; j < str.size(); j++) {
			map[i][j] = str[j] - '0';
		}
	}

	memset(visit, -1, sizeof(visit));
	cout << BFS();
}