[BOJ] 16933 : 벽 부수고 이동하기 3 - travelbeeee

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

---

BFS

● BFS 탐색을 진행하는데 벽을 몇 번 부수고 현재 지점에 도달했는지 체크하기위해 3차원 visited 배열을 사용하면 된다.

● visited[x][y][w] := (x, y) 지점에 w만큼의 벽을 부수고 도달

● 현재 지점에서 이동할 다음 칸이 벽이 아니고 방문하지 않았다면 큐에 push.

    현재 지점에서 이동할 다음 칸이 벽이라면

    - 낮인 경우, 이동할 칸에 현재 벽 부순 횟수 + 1 상태로 방문한 적이 없다면 큐에 push

    - 밤인 경우, 이동할 칸에 현재 벽 부순 횟수 + 1 상태로 방문한 적이 없다면 큐에 현재 위치를 push

#include<iostream>
#include<queue>

using namespace std;

struct node {
	int x, y, t, w; // x좌표 y좌표 벽부순횟수 시간
};

int N, M, K, dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, -1, 0, 1 };
char map[1000][1001];
bool visited[1000][1000][11] = {};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> M >> K;
	for (int i = 0; i < N; i++)
		cin >> map[i];

	queue<node> q;
	q.push({ 0, 0, 0, 0});
	visited[0][0][0] = 1;

	int ans = -1;
	while (!q.empty()) {
		int curX = q.front().x, curY = q.front().y;
		int curTime = q.front().t, curW = q.front().w;
		q.pop();
		if (curX == N - 1 && curY == M - 1) {
			ans = curTime + 1;
			break;
		}
		for (int i = 0; i < 4; i++) {
			int nextX = curX + dx[i], nextY = curY + dy[i];
			if (!(0 <= nextX && nextX < N && 0 <= nextY && nextY < M))
				continue;
			if (map[nextX][nextY] == '0' && !visited[nextX][nextY][curW]) {
				visited[nextX][nextY][curW] = 1;
				q.push({ nextX, nextY, curTime + 1, curW });
			}
			if (map[nextX][nextY] == '1' && curTime % 2 == 0 && curW + 1 <= K && !visited[nextX][nextY][curW + 1]) {
				visited[nextX][nextY][curW + 1] = 1;
				q.push({ nextX, nextY, curTime + 1, curW + 1});
			}
			if (map[nextX][nextY] == '1' && curTime % 2 == 1 && curW + 1 <= K && !visited[nextX][nextY][curW + 1]) {
				q.push({ curX, curY , curTime + 1, curW });
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

---