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

링크

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

2206번: 벽 부수고 이동하기

해설

이 문제는 그래프 문제이고, 가중치가 없으므로 BFS를 이용해서 푸는 문제입니다.

다만 평범한 BFS 와는 조금 다르게 벽을 부수기를 실행한 그래프와 하지않은 그래프 두가지를 사용해야합니다.

그래서 queue 에도 현제 좌표 뿐만 아니라 벽을 부술 수 있는지 없는지 또한 같이 저장합니다.

 

table[ x위치 ][ y위치 ][ 벽부술수있는가 ]

로 table 을 만들고 시작은 table[0][0][1] 에서 시작합니다.

 

그후 매번 queue 에서 현제위치를 꺼내와서

1. 다음 위치가 배열을 안 벗어나는가?

2-1. 다음 위치가 아직 가지 않은 지점이면 그냥 queue 에 넣고 갑니다.

2-2. 벽이면 벽부수기를 실행하고 table[][][0] 으로 내려갑니다.

      (당연히 벽부수기를 이미 했다면 못갑니다)

 

계속 반복하다가 N-1 , M-1 지점에 도착하면 멈춥니다.

 

아래 코드에서는

-1 = 벽

0 = 아직 지나가지않은곳

1~ = 이미 지나간곳

으로 사용했습니다.

 

이렇게 코드를 짜면 벽을 부수지 않은 그래프, 벽을 부순 그래프 각자대로 최선을 다해 가다가

먼저 도착하면 끝이나겠죠?

 

코드

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

typedef struct _state {
	int x, y;
	bool bomb;
}state;

int N, M, table[1000][1000][2];
int dx[4] = { 1, -1, 0, 0 },
	dy[4] = { 0, 0, 1, -1 };

bool can_go(int _x, int _y) {
	return 0 <= _x && _x < N && 0 <= _y && _y < M;
}

int bfs() {

	table[0][0][1] = 1;
	queue<state> que;
	que.push({ 0, 0, true });

	while (!que.empty()) {
		state now = que.front();
		if (now.x == N - 1 && now.y == M - 1)
			return table[now.x][now.y][now.bomb];
		que.pop();
		int bomb = now.bomb;

		for (int i = 0; i < 4; ++i) {
			int nx = now.x + dx[i];
			int ny = now.y + dy[i];
			
			if (can_go(nx, ny)) {
				if (table[nx][ny][bomb] == 0) {
					table[nx][ny][bomb] = table[now.x][now.y][bomb] + 1;
					que.push({ nx, ny, now.bomb });
				}
				else if (table[nx][ny][1] == -1 && now.bomb) {
					table[nx][ny][0] = table[now.x][now.y][1] + 1;
					que.push({ nx, ny, false });
				}
			}
		}

	}
	
	return -1;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			char ch;
			cin >> ch;
			int val;
			if (ch == '1')
				val = -1;
			else
				val = 0;
			table[i][j][0] = val;
			table[i][j][1] = val;
		}
	}
	cout << bfs();
	return 0;
}