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

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

14442번: 벽 부수고 이동하기 2

1. 주의할 점

- K의 값이 0~10이므로 방문 배열 Check[1000][1000][11]로 설정한다

- 출발지점도 포함이다

 

2. 구현

- 구조체를 이용하여 X좌표, Y좌표, 벽을 부순 횟수를 저장하는 Queue를 통해 BFS 탐색을 한다

- 4방향을 탐색하며, 벽이 아닌 경우 현재 벽을 부순 횟수로 이동하려는 지점을 방문한 적이 없다면 Queue에 추가하고, 방문한 적이 있다면 무시한다.

- 다음 지점이 벽인 경우, 벽을 부술 수 있는 횟수가 남아있으며, 현재 벽을 부순 횟수+1의 횟수로 이동하려는 지점을 방문한 적이 없다면 Queue에 추가, 있다면 무시한다.

 

#include <iostream>
#include <queue>
#include <string>
using namespace std;
int arr[1000][1000];
int check[1000][1000][10];
struct info {
	int x, y, wall;
};
info tmp;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

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;
	q.push(tmp);
	check[0][0][0] = 1;
	int result = -1;
	while (!q.empty()) {
		int cx = q.front().x;
		int cy = q.front().y;
		int cw = q.front().wall;
		q.pop();
		if (cx == col - 1 && cy == row - 1) {
			result = check[cy][cx][cw];
			break;
		}
		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]==0) {
					check[ny][nx][cw] = check[cy][cx][cw] + 1;
					tmp.x = nx;
					tmp.y = ny;
					tmp.wall = cw;
					q.push(tmp);
				}
				else if(arr[ny][nx]==1 && check[ny][nx][cw+1]==0 && cw<crash){
					check[ny][nx][cw + 1] = check[cy][cx][cw] + 1;
					tmp.x = nx;
					tmp.y = ny;
					tmp.wall = cw + 1;
					q.push(tmp);
				}
			}
		}
	}
	cout << result;
	system("pause");
	return 0;
}