boj, 백준) 16933. 벽 부수고 이동하기 3 ( C/C++ )

1. 문제 링크

www.acmicpc.net/problem/16933

16933번: 벽 부수고 이동하기 3

2. 문제 개요

NxM의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 나는 (1, 1)에서 (N, M)의 위치까지 이동하려고 하는데, 이때 최단 경로로 이동하려 한다.

 

이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다. 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.

 

만약, 이동하는 도중 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다. 단, 벽은 낮에만 부술 수 있다.

 

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

 

3. 문제 힌트

우선, BFS를 사용해서 배열을 탐색.

 

벽을 만났을 경우, 부술 수도 있고, 부수지 않을 수도 있음. (모든 상태 갖고 있어야 함)

벽을 0번 부순 상태의 움직임, 벽을 1번, ..., K번 부순 상태에서의 움직임이 있을 수 있음.

 

해당 칸을 낮에 도착하는 경우, 밤에 도착하는 경우 존재.

 

 

4. 문제 풀이

모든 상태를 가지고 있어야 한다. 벽을 n번 부숴왔고 아직 몇 번 더 부술 수 있다거나, 더 이상은 못 부순다 라는 것을 알기 위해서!

 

그리고 해당 칸을 밤에 올 수도 있고, 낮에 올 수도 있기 때문에 2개의 추가적인 상태가 필요하다.

그래서 방문을 나타내는 배열을 다음과 같이 나타냈다.

 

[열][행][밤/낮][벽 부순 횟수]

[N][M][2][K]이다.

N, M은 최대 1000, 밤과 낮은 2, K는 최대 10 이기 때문에,

BFS를 수행하는데 N*M*2*K = 최대 2*10^7이고, 제한시간 내에 풀 수 있다는 것을 알 수 있다.

 

이  부분만 잘 캐치하고 있다면 다른 BFS문제와 별 다를 것이 없다.

 

현재 장소에서 다음 장소로 이동할 때,

 

크게

벽이 있거나 없거나로 나뉘게 되고,

 

벽이 있을 때, 부술 것인지, 부수지 않을 것인지,

 

부순다고 했을 때, 밤인지, 낮인지,

등을 잘 체크해주면 된다.

 

그래서, queue의 front가 목적지 (N, M)이라면, 바로 BFS를 멈추고 움직인 횟수를 출력해주면 된다.

탐색을 다 했는데도 목적지에 도달하지 못했다면 최단경로(거리)는 없는 것이고, -1을 출력해주자.

 

5. 코드

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

struct COORD {
	COORD(){}
	COORD(int y_, int x_, int day_, int breaktime_, int time_) :y(y_), x(x_), day(day_), breaktime(breaktime_), time(time_) {}
	int y, x;
	int day;
	int breaktime, time;
};

bool visited[1000][1000][2][10];//0 : day , 1: night
char map[1000][1000];
int n, m, k, ans = -1;
queue<COORD> q;

const int dx[] = { 0,1,-1,0,0 };
const int dy[] = { 0,0,0,1,-1 };

int main()
{
	scanf("%d %d %d", &n, &m, &k);

	for (int i = 0; i < n; ++i)
		scanf("%s", map[i]);

	//bfs
	q.push(COORD(0, 0, 0, 0, 1));
	visited[0][0][0][0] = true;

	while (!q.empty()) {
		COORD cur = q.front();
		q.pop();
		if (cur.y == n - 1 && cur.x == m - 1)
		{
			ans = cur.time;
			break;
		}
		for (int dir = 0; dir < 5; ++dir) 
		{
			COORD next;
			next.y = cur.y + dy[dir];
			next.x = cur.x + dx[dir];
			if (cur.day == 1)	
				next.day = 0;
			else
				next.day = 1;
			next.breaktime = cur.breaktime;
			next.time = cur.time + 1;

			//outside of map & visited place
			if (next.y >= n || next.x >= m || next.x < 0 || next.y < 0 || visited[next.y][next.x][next.day][next.breaktime])
				continue;


			if (map[next.y][next.x] == '0') {
				visited[next.y][next.x][next.day][next.breaktime] = true;
				q.push(next);
			}
			else
			{//wall
				if (dir == 0) {
					visited[next.y][next.x][next.day][next.breaktime] = true;
					q.push(next);
				}
				else if (cur.day == 0 && cur.breaktime < k) {
					++next.breaktime;
					visited[next.y][next.x][next.day][next.breaktime] = true;
					q.push(next);
				}
			}
		}
	}

	printf("%d", ans);



	return 0;
}

6. 결과