(c++)백준 2206번: 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

[풀이]

기존의 최단 경로를 구하는 bfs를 쓰지만, visited를 3차원 배열로 선언하여 그 좌표를 벽을 1번 부수고 방문했는지와 부수지 않고 방문했는지 여부를 표시해줬다.

 

#include <iostream>
#include <queue>
#include <cstdio>//scanf
using namespace std;

struct State {
	int x, y;
	int b_cnt, p_len;//벽을 부순 횟수, 이동한 거리
};

int N, M;
int Map[1001][1001];
bool visited[1001][1001][2];//x좌표, y좌표, 벽을 부순 적 있는지
const int dx[] = { -1,1,0,0 };//상하
const int dy[] = { 0,0,-1,1 };//좌우

int bfs() {
	queue<State>q;
	q.push({ 0,0,0,1 });
	visited[0][0][0] = true;
	int ans = -1;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int b_cnt = q.front().b_cnt;
		int p_len = q.front().p_len;
		q.pop();
		if (x == N - 1 && y == M - 1) {
			ans = p_len;
			break;
		}
		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)
				continue;
			//다음 칸이 벽인데 아직 벽 안 부쉈을 때
			if (Map[nx][ny] == 1 && b_cnt == 0) {
				visited[nx][ny][b_cnt + 1] = true;
				q.push({ nx,ny,b_cnt + 1,p_len + 1 });
			}
			else if (Map[nx][ny] == 0 && visited[nx][ny][b_cnt] == false) {
				visited[nx][ny][b_cnt] = true;
				q.push({ nx,ny,b_cnt,p_len + 1 });
			}
		}
	}
	return ans;
}

void solution() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &Map[i][j]);
		}
	}
	cout << bfs() << '\n';
}

int main() {
	solution();
	return 0;
}