[백준 16933] 벽 부수고 이동하기 3 (C++)

문제 링크: https://www.acmicpc.net/problem/16933

16933번: 벽 부수고 이동하기 3

1. 주의할 점

- BFS를 잘못 사용할 경우 시간초과가 발생한다

- K의 값이 0~10이므로 Check[1000][1000][11]로 설정해야 한다 -> 11 대신 10을 사용할 경우 틀린다

- 낮의 경우에만 벽을 부술 수 있다

 

2. 구현

- 벽 부수고 이동하기 1이나 2와 비슷한 방법을 사용하지만, 낮과 밤의 구분을 추가한다

- 낮일 경우(Sun: True) 벽을 부수고 이동할 수 있다

- 밤일 경우(Sun: False) 벽을 부수지 못하므로, 다음 이동칸이 벽이고 벽을 부술 수 있는 횟수가 남아있을 때 Blocked의 값을 True로 바꾼다

Block의 값이 True일 경우, 해당 칸을 큐에 추가한다.

-> 위의 경우를 만족할때마다 큐에 추가하지 않는 이유: 큐에 같은 요소가 최대 4개 쌓일 수 있다.

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

struct info {
	int x, y, wall, dist;
};
info tmp;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int arr[1000][1000];
bool check[1000][1000][11] = { false, };

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int row, col, crash;
	string s;
	cin >> row >> col >> crash;
	for (int i = 0; i < row; i++) {
		cin >> s;
		for (int j = 0; j < col; j++) 
			arr[i][j] = s[j] - '0';		
	}
	queue<info> q;
	tmp.x = 0;
	tmp.y = 0;
	tmp.wall = 0;
	tmp.dist = 1;
	q.push(tmp);
	check[0][0][0] = true;
	int result = -1;
	bool sun = true;
	while (!q.empty()) {
		int len = q.size();
		for(int k=0;k<len;k++) {
			int cx = q.front().x;
			int cy = q.front().y;
			int cw = q.front().wall;
			int cd = q.front().dist;
			q.pop();
			if (cy == row - 1 && cx == col - 1) {
				result = cd;
				break;
			}
			bool block = false;
			for (int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				if (nx >= 0 && ny >= 0 && nx < col && ny < row) {
					if (arr[ny][nx] == 0 && !check[ny][nx][cw]) {
						check[ny][nx][cw] = true;
						tmp.x = nx;
						tmp.y = ny;
						tmp.wall = cw;
						tmp.dist = cd + 1;
						q.push(tmp);
					}
					else if (arr[ny][nx] == 1 && !check[ny][nx][cw + 1] && cw < crash) {
						if (sun) {		//낮
							check[ny][nx][cw + 1] = true;
							tmp.x = nx;
							tmp.y = ny;
							tmp.wall = cw + 1;
							tmp.dist = cd + 1;
							q.push(tmp);
						}
						else 
							block = true;						
					}
				}
			}
			if (block) {
				tmp.x = cx;
				tmp.y = cy;
				tmp.dist = cd + 1;
				tmp.wall = cw;
				q.push(tmp);
			}
		}
		if (result > 0) break;
		sun = !sun;
	}
	cout << result;
	system("pause");
	return 0;
}