백준14442 - 벽 부수고 이동하기 2

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

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

bfs를 이용하여 푼 문제이다.

 

bfs를 만들 때 방문 여부는 3차원 배열을 이용하여 체크해야 한다. (x, y)에 도달하는데 k개의 벽을 부수고 도달했다는 것으로 방문여부를 만든다.

 

큐에 원소로 클래스를 만들어 (x, y)에 도달하는데 총 부순 벽의 수는 k개이고 건너간 칸의 갯수는 t라고 설정한다.

 

입력에서 주어진 벽의 갯수이하로 벽을 부수고 최종 목적지에 도달하는 최소 칸의 갯수를 찾으면 된다. 다음 공간으로 이동할 때는 상하좌우로 이동한다. 벽을 만난다면 벽의 갯수를 하나 늘리고 차지한 칸의 갯수를 하나 늘린채로 다음 도달할 곳을 큐에 넣어주고 빈 공간을 만난다면 벽의 갯수는 그대로 두고 차지한 칸의 갯수를 하나 늘린채로 다음 도달할 곳을 큐에 넣어준다. 두가지 모두 다음 (x, y)에 도달했을 때 k개의 벽을 부수고 도달하였다고 방문 여부를 true로 바꾼다.

#include <iostream>
#include <queue>
#include <string.h>
#include <algorithm>
#define MAX 1001
using namespace std;

//(x, y)까지 벽을 총 k개 부셨고 총 t칸 먹었다.
class Point {
public:
	int x, y, k, t;
	Point(int x, int y, int k, int t) {
		this->x = x;
		this->y = y;
		this->k = k;
		this->t = t;
	}
};
int n, m, wall; //가로 n, 세로 m, 최대로 부실 수 있는 벽의 갯수 wall
int mat[MAX][MAX]; //좌표 정보
bool visit[MAX][MAX][11]; //(x, y)에 도착했을 때 총 부신 벽의 개수가 k인 경우 방문 여부
string s;

//상하좌우
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

int small = 987654321; //벽을 최소로 부수고 가장 빨리 도착한 시간

void bfs(int x, int y, int k, int t) {
	queue<Point> q;
	q.push(Point(x, y, k, t)); //(0, 0)까지 벽 0개 부수고 총 1칸 먹었다.
	visit[x][y][0] = true; //(0 ,0)에 벽 0개 부셔서 도착했다고 체크

	while (!q.empty()) {
		//첫번째 원소를 추출해서 삭제
		x = q.front().x;
		y = q.front().y;
		k = q.front().k;
		t = q.front().t;
		q.pop();

		if (n == x && m == y) { //제일 마지막 칸에 도착하면
			small = min(small, t); //최소를 찾는다.
			continue; //다음 큐로 이동
		}

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (1 <= nx && nx <= n && 1 <= ny && ny <= m) { //유효한 좌표 범위이면
				if (mat[nx][ny] == 1 && k + 1 <= wall && !visit[nx][ny][k + 1]) { //다음에 이동할 곳이 벽이고 벽을 부순 갯수가 wall보다 적고 k + 1개 부순 채로 방문하지 않았다면
					q.push(Point(nx, ny, k + 1, t + 1)); //다음 이동할 곳을 벽을 한 개 더 부수고 t + 1칸 먹었다고 큐에 삽입
					visit[nx][ny][k + 1] = true; //다음에 이동할 곳을 k + 1개 부순채로 방문했다고 체크
				}
				else if (mat[nx][ny] == 0 && !visit[nx][ny][k]) { //다음에 이동할 곳이 빈칸이고 k개 부순채로 방문하지 않았다면
					q.push(Point(nx, ny, k, t + 1)); //다음 이동할 곳을 t + 1칸 먹었다고 
					visit[nx][ny][k] = true; //다음에 이동할 곳을 k개 부순채로 방문했다고 체크
				}
			}
		}

	}
}

int main() {
	cin >> n >> m >> wall;
	for (int i = 1; i <= n; i++) {
		cin >> s;
		for (int j = 1; j <= m; j++) {
			mat[i][j] = s[j - 1] - '0';
		}
	}

	memset(visit, false, sizeof(visit)); //벽을 부수고 도달한 모든 공간을 방문하지 않았다고 초기화 

	bfs(1, 1, 0, 1); //탐색

	if (small == 987654321) { //도달 못했으면 
		cout << -1; //-1
	}
	else { //도달 했으면
		cout << small; //최솟값 출력
	}
}