[BOJ] 14442 : 벽 부수고 이동하기 2 - travelbeeee

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

---

BFS 탐색

● 단순 BFS 탐색을 수행해서 (0, 0) 에서 ( N - 1, M - 1 ) 까지 이동이 가능한지 탐색하면 되는데 최대 K 개 만큼의 벽을 부셔도 되므로, visited 배열을 2차원이 아닌 3차원으로 visited[N][M][K] 로 만들어줘야합니다.

visited[X][Y][T] := (X, Y) 지점에 벽을 T개 부수고 도착한 적이 있는지 없는지.

● 큐에는 현재 내 위치 좌표와 몇 번 벽을 부수고 이동했는지, 이동 횟수 총 4가지 정보를 담습니다.

queue<pair<pair<int, int>, pair<int, int>> q;

● 내가 이동해야하는 곳이 '1' 벽이라면 현재 벽을 부순 횟수 + 1 이 K 이하인지 체크하고, visited[curX][curY][현재벽을부순횟수 + 1] 을 방문하지 않았다면 큐에 담아줍니다.

● 내가 이동해야하는 곳이 '0' 이라면 visited[curX][curY][현재벽을부순횟수] 를 방문하지 않았다면 큐에 담아줍니다.

#include<iostream>
#include<queue>

using namespace std;

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

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<pair<pair<int, int>, pair<int, int>>> q;
	visited[0][0][0] = 1;
	q.push({ {0, 0}, { 0, 0 } });

	bool flag = false;
	while (!q.empty()) {
		pair<pair<int, int>, pair<int, int>> temp = q.front();
		q.pop();
		int curX = temp.first.first, curY = temp.first.second;
		int curW = temp.second.first, curL = temp.second.second;
		
		if (curX == N - 1 && curY == M - 1) {
			cout << curL + 1 << '\n';
			flag = true;
			break;
		}
		for (int i = 0; i < 4; i++) {
			int nX = curX + dx[i], nY = curY + dy[i];
			if (!(0 <= nX && nX < N && 0 <= nY && nY < M))
				continue;
			if (map[nX][nY] == '0' && visited[nX][nY][curW] == 0) {
				visited[nX][nY][curW] = 1;
				q.push({ {nX, nY}, {curW, curL + 1} });
			}
			if (map[nX][nY] == '1' && visited[nX][nY][curW + 1] == 0 && curW + 1 <= K){
				visited[nX][nY][curW + 1] = 1;
				q.push({ {nX, nY}, {curW + 1, curL + 1} });
			}
		}
	}
	if (!flag)
		cout << -1 << '\n';
	return 0;
}

---