[백준] 16933 벽 부수고 이동하기 3

[문제이해]

1. NxM 으로 표현되는 map이 있다. (0은 이동할 수 있는 공간이고, 1은 이동할 수 없는 벽이다.)

2. 당신은 (1,1)에서 (N,M)위치로  최단 경로로 이동 해야한다.

3. 이 문제에는 낮과 밤이 존재한다. 가장 처음에 이동할 때는 낮이고, 이동할 때마다 낮과 밤이 바뀐다.

4. 이동하지 않고 같은 칸에 머무를 수 있는데, 이때도 낮과 밤이 바뀐다.

3. map에서 벽을 만나면, 벽을 부술 수 있다. (벽은 최대 k개 만큼 부술 수 있다.)

4. 단, 벽은 아침에만 부술 수 있다.

5. map이 주어지고 N, M, k가 주어졌을 때 최단 경로를 구해내야 한다.

 

[설계]

1. 최단경로를 구하는 문제이므로 BFS를 사용하여 구현한다.

2. BFS로 방문하는 정점의 정보는 4가지이다. (x좌표, y좌표, 벽을 부순 횟수, 낮(0) or 밤(1))

3. Ex1) (0, 0, 0, 0) 은 (0,0)에서 벽을 0번 부쉈고 낮(0)인 상태이다.

4. Ex2) (0, 0, 0, 1) 은 (0,0)에서 벽을 0번 부쉈고 밤(1)인 상태이다.

5. Ex3) (4, 3, 5, 0) 은 (4,3)에서 벽을 5번 부쉈고 낮(0)인 상태이다.

6. 즉, 정점의 상태는 4가지로 표현된다. 

7. 따라서 BFS 방문처리 배열은 아래와 같은 4차원 배열을 사용한다.

    visited[x좌표][y좌표][벽을 부순 횟수][낮(0) or 밤(1)]

8. 그 외 이동하지 않고 같은 칸에 머무를 수 있는 것, 벽은 아침에만 부술 수 있는 것, 벽은 최대 k개 만큼 부술 수 있는 것, 시작할때는 낮이고 이동할 때마다 낮과 밤이 바뀌는 것 등을 고려하여 BFS를 구현하면된다.

 

[회고]

- 정점의 상태를 정의하니까 풀기 수월했다.

- 조건이 여러개라 복잡했지만 차근차근 풀어나갔다.

 

[소스]

#include<iostream>
#include<queue>
using namespace std;

typedef struct {
	int x, y, broken, day; 
}pos;

int n, m, k;
int res = 1e9;
int map[1000][1000];
int visited[1000][1000][11][2];
int dx[] = { -1,1,0,0,0 }, dy[] = { 0,0,-1,1,0 };

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

	while (!q.empty()){
		int x = q.front().x, y = q.front().y;
		int broken = q.front().broken, day = q.front().day;
		int nextDay;

		if (day == 0) nextDay = 1;
		else nextDay = 0;

		q.pop();

		if (x == n - 1 && y == m - 1) {
			res = min(res, visited[x][y][broken][day]);
		}

		for (int i = 0; i < 5; i++) {
			int nx = x + dx[i], ny = y + dy[i];
			if (nx >= n || nx < 0 || ny >= m || ny < 0) continue;
			
			if(x == nx && y== ny){
				if (visited[nx][ny][broken][nextDay] == 0) {
					visited[nx][ny][broken][nextDay] = visited[nx][ny][broken][day] + 1;
					q.push({ nx,ny,broken,nextDay });
				}
			}
			else if (map[nx][ny] == 0 && visited[nx][ny][broken][nextDay] == 0) {
				visited[nx][ny][broken][nextDay] = visited[x][y][broken][day] + 1;
				q.push({ nx, ny, broken, nextDay });
			}
			else if (map[nx][ny] == 1 && visited[nx][ny][broken + 1][nextDay] == 0) {
				if (day == 1) continue;
				if (broken + 1 > k) continue;
				visited[nx][ny][broken + 1][nextDay] = visited[x][y][broken][day] + 1;
				q.push({ nx, ny, broken + 1,nextDay });
			}
		}
	}
}

int main() {

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf_s("%1d", &map[i][j]);
		}
	}

	bfs();

	if (res == 1e9)
		cout << -1;
	else
		cout << res;

	return 0;
}