[BOJ]백준 1442번: 벽 부수고 이동하기 2/BFS

www.acmicpc.net/problem/14442

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

벽 부수고 이동하기 시리즈

이전에는 벽을 한 개만 부술 수 있었는데, 이번에는 벽을 최대 k개 부술 수 있다.

말이 되고픈 원숭이 문제(2jinishappy.tistory.com/144)와 같이, visit배열을 3차원으로 관리서 벽을 k개 부쉈을 때의 방문 여부를 체크해 주어야 한다.

 

구조체 변수 순서 헷갈리고 배열 선언 제대로 안 해서 헤맸다....^^

 

#include <cstdio>
#include <queue>
using namespace std;
typedef struct { int w,x, y,d; }point;
int n, m, k;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
bool map[1001][1001], visit[11][1001][1001];
queue<point> q;
bool safe(int x, int y) { return x >= 0 && x < m && y >= 0 && y < n; }
int bfs() {
	visit[0][0][0] = 1;
	q.push({ 0,0,0,1 });
	while (!q.empty()) {
		point cur = q.front(); q.pop();
		if (cur.x == m - 1 && cur.y == n - 1)return cur.d;

		for (int i = 0; i < 4; i++) {
			int nx = cur.x + dx[i], ny = cur.y + dy[i];
			
			if (!safe(nx, ny))continue;

			if (map[ny][nx]) {
				if (cur.w >= k|| visit[cur.w + 1][ny][nx])continue;
				visit[cur.w + 1][ny][nx] = 1;
				q.push({ cur.w + 1,nx,ny,cur.d+1 });
			}
			else {
				if (visit[cur.w][ny][nx])continue;
				visit[cur.w][ny][nx] = 1;
				q.push({ cur.w,nx,ny,cur.d + 1 });
			}
		}
	}
	return -1;
}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for(int i=0;i<n;i++)
		for (int j = 0,a; j < m; j++) {
			scanf("%1d", &a);
			if (a)map[i][j] = 1;
			else map[i][j] = 0;
		}
	printf("%d", bfs());
	return 0;
}