백준2206 벽 부수고 이동하기 - C++

오늘은 BFS의 살~~~~~~~~~~~~~~~~~~짝 응용판이다.

 

(1,1) => (N, M)까지 도착하는 최단경로이고

맵이 1000x1000이기 때문에 DFS로 접근하기엔 크다.

고로 BFS 로 접근해 보자.

 

양방향 탐색으로 조금 더 빠르게 풀 수도 있겠지만

머리 아프므로 그냥 BFS로 풀어보자.

 

조금 어려운 부분은 벽을 한 번 부술 수 있다는 점이다.

아무리 벽으로 막혀있어도 한 번은 부수고 지나갈 수 있으니

벽을 부순다는 점을 기록할 판을 하나 추가로 마련하자.

 

그래서 내가 이동한 횟수를 기록하는 dp 배열을 만들건대,

벽을 한 번도 부수지 않은 상태와 

벽을 한 번 부순 상태는 다르기 때문에

한 번도 부수지 않은 상태는 dp [x][y][0]에 저장하고

부수고 지나온 상태는 dp [x][y][1]에 저장하겠다.

 

즉, dp [5][6][1] 은 (5,6) 지점까지 벽을 한 번 부수고 올 때

가장 최단 거리이고

dp [5][6][0] 은 (5,6) 지점까지 벽을 한 번도 부수지 않고 왔을 때

최단 거리를 저장한다.

 

그렇다면 map [x+1][y] = 1 (벽) 일 때 (x, y)에서 (x+1, y)로 이동할 수 있는 경우는

벽을 부순 적이 없을 때뿐이고, 

벽을 부순 적이 있다면 지나가지 못할 것이다.

이것을 if 문으로 잘 처리해 보자.

#include <cstdio>
#include <string> //pair 사용 목적

#define INF 987654321 // 절대 나올 수 없는 큰 숫자

using namespace std;

int N, M;

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

int dp[1001][1001][2]; //[x][y][벽 부순 횟수]
int map[1001][1001];
//<벽 부순적 있는지, 이동횟수>, <x , y>
//이동횟수는 가지고 다닐 필요 없지만 알기 쉽게 가지고 다니는 걸로.
//queue 구현
pair<pair<bool,int>, pair<int, int>> q[2000001];
int s, e;
void push(pair<pair<bool,int>, pair<int, int>> a) {
	q[e++] = a;
}
void pop() {
	++s;
}
bool empty() {
	return s == e;
}

void bfs() {
//초기값 <벽 부순 적 없음, 이동횟수 1>, <x, y>
	push({ {false,1}, {1,1} });
    //첫 출발지는 항상 이동횟수가 1
	dp[1][1][0] = dp[1][1][1] = 1;
	//q가 빌 때까지
	while (!empty()) {
		//queue 에서 빼내기
		int cx = q[s].second.first;
		int cy = q[s].second.second;
		bool isBrakeWall = q[s].first.first;
		int curMove = q[s].first.second;
		pop();

		//4방향 중 갈 곳 정하기
		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			//맵밖으로 나가면 안됨
			if (nx <1 || nx>N || ny<1 || ny>M) continue;
			//막힌 벽인데 이미 한 번 벽을 부쉈다면 못감
			if (map[nx][ny] == 1 && isBrakeWall) continue;
			//가려는 곳이 이미 왔고, 더 멀리 돌아서 왔다면 갈 필요 없음
			if (map[nx][ny] == 0) {
				if (dp[nx][ny][isBrakeWall] <= curMove + 1) {
					continue;
				}
				dp[nx][ny][isBrakeWall] = curMove+1;
				//도착한 경우 push 안함
				if (nx == N && ny == M) continue;

				push({ {isBrakeWall, curMove + 1}, {nx,ny} });
			}
			else {
            //벽으로 막혀있고, 벽을 부순적 없는 경우
				if (dp[nx][ny][1] <= curMove+1) {
					continue;
				}
				dp[nx][ny][1] = curMove + 1;
				if (nx ==N && ny ==M)continue;
				push({ {true, curMove + 1}, {nx,ny} });
			}
		}
	}
	
}

int solve() {
	bfs();
// 벽을 부순 경우와 부수지 않은 경우 중 더 작은 것
	int ans = dp[N][M][1] > dp[N][M][0] ? dp[N][M][0] : dp[N][M][1];
	return ans == INF ? -1 : ans; //도착 못했다면 -1
}

int main() {
	scanf("%d %d", &N, &M);

	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= M; ++j) {
			scanf("%1d", &map[i][j]);
			dp[i][j][0] = dp[i][j][1] = INF;
		}
	}

	printf("%d\n", solve());
}