(c++)백준 14442번: 벽 부수고 이동하기 2

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

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

[풀이]

1.최단 거리 구하는 문제이므로 bfs 사용

2.queue에 x좌표, y좌표, 벽을 부순 횟수, 이동거리 저장 

3.벽을 만나면 무시하는 게 아니라 K번 이하로 벽을 부술 수 있으므로 visited를 3차원 행렬로 선언

4.벽을 n번 부수고 (x,y)좌표에 방문했으면 visited[x][y][n] = true

5.(N-1, M-1)에 도착하면 이동거리 반환

 

#include <iostream>
#include <queue>
#include <cstdio>//scanf
using namespace std;

struct State {
	int x, y;
	int b_cnt, p_len;//벽을 부순 횟수, 이동한 거리
};

int N, M, K;
int Map[1000][1000];
bool visited[1000][1000][11] = { false, };//x좌표, y좌표, 벽을 부순 적 있는지
const int dx[] = { -1,1,0,0 };//상하
const int dy[] = { 0,0,-1,1 };//좌우

int bfs() {
	queue<State>q;
	q.push({ 0,0,0,1 });
	visited[0][0][0] = true;
	int ans = -1;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int b_cnt = q.front().b_cnt;
		int p_len = q.front().p_len;
		q.pop();
		if (x == N - 1 && y == M - 1) {
			ans = p_len;
			break;
		}
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M)
				continue;
			//다음 칸이 벽인데 아직 벽 K번 안 부쉈을 때
			if (Map[nx][ny] == 1 && b_cnt < K && visited[nx][ny][b_cnt] == false) {
				visited[nx][ny][b_cnt + 1] = true;
				q.push({ nx,ny,b_cnt + 1,p_len + 1 });
			}
			else if (Map[nx][ny] == 0 && visited[nx][ny][b_cnt] == false) {
				visited[nx][ny][b_cnt] = true;
				q.push({ nx,ny,b_cnt,p_len + 1 });
			}
		}
	}
	return ans;
}

void solution() {
	cin >> N >> M >> K;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &Map[i][j]);
		}
	}
	cout << bfs() << '\n';
}

int main() {
	solution();
	return 0;
}