[ BAEKJOON] 2206번 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

 

문제조건

1. (1,1) 에서 (n,m)까지 최단경로
2. 벽을 하나까지 부술수있다.

조건 2 때문에 일반적인 bfs로 풀수가 없다.

벽은 부숴도 되고, 안부숴도되고 그렇다면 어떻게 하지,,? 생각을 해보면 bfs자체가 수행될때마다 최단거리를 의미하고, 그에따라 queue에 넣을 조건만 추가해주면 된다. 벽은 하나까지 부술수있으므로, 배열을 3차원배열로 만들어주고, queue에도 (x,y, block) 세가지를 넣어줘서 벽이 막혀있는경우 / 막혀있지 않은 경우로 나누어 풀어줬다.

 

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

int n, m, map[1001][1001], visited[1001][1001][2], dist[1001][1001][2];
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, -1, 0, 1 };

struct s {
	int y, x, block;
};

int bfs() {
	queue<s> q;
	q.push({ 0,0 ,1});
	visited[0][0][1] = 1;
	dist[0][0][1] = 1;
	while (!q.empty()) {
		int y = q.front().y;
		int x = q.front().x;
		int block = q.front().block;
		q.pop();
		if (y == n - 1 && x == m - 1) return dist[n - 1][m - 1][block];
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
			if (map[ny][nx] == 0 && !visited[ny][nx][block]) {
				visited[ny][nx][block] = 1;
				q.push({ ny,nx, block });
				dist[ny][nx][block] = dist[y][x][block] + 1;
			}
			if (map[ny][nx] == 1 && block) {
				visited[ny][nx][block-1] = 1;
				dist[ny][nx][block - 1] = dist[y][x][block] + 1;
				q.push({ ny,nx,block -1 });
			}
		}
	}
	return -1;
}

// 0 : 이동가능  /  1 : 이동 불가
int main(){
	int res = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < m; j++) {
			map[i][j] = s[j] - '0';
		}
	}
	cout << bfs();
}

 

이렇게 풀게되면 벽을 부쉈는지 안부쉈는지 난 알 수 없지만, 계산했을때, 더 빨리 도착하는 것을 리턴 시켜준다.

물론 저때 block 값 출력하면 알 수는 있지만,, 문제 풀이가 목적이기에