[BOJ]16933번: 벽 부수고 이동하기 3 (c++)

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

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

 

 

left : 벽을 부술 수 있는 개수

bfs + map[x][y]에 도착했을 때의 left 값을 기록하며 비교 + time 기준으로 분기

 

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

struct pos {
	int x, y;
};

struct info {
	pos p;
	int left, dist, time;
};

int N, M, K;
const int MAX = 1000;
char map[MAX][MAX + 1];
int visit[MAX][MAX];
int dr_x[] = { 0, 1, 0, -1 };
int dr_y[] = { 1, 0, -1, 0 };
enum { NIGHT = -1, DAY = 1 };

int bfs()
{
	// visit : 여분의 부술 벽 개수를 저장할 배열 
	// -1값으로 초기화
	memset(visit, -1, sizeof(visit));

	// map[0][0]부터 <부술수 있는 벽 K개, 이동횟수 1, 낮>으로 시작
	queue<info> q;
	q.push({ 0, 0, K, 1, DAY });

	// map[0][0]에 도착했을 때 부술 수 있는 벽 개수 K개
	visit[0][0] = K;

	while (!q.empty())
	{
		pos p = q.front().p;
		int left = q.front().left;
		int dist = q.front().dist;
		int time = q.front().time;
		q.pop();

		// map[N - 1][M - 1]에 도착하면 이동횟수 반환
		if (p.x == N - 1 && p.y == M - 1)
		{
			return dist;
		}

		// 4방향 탐색
		for (int i = 0; i < 4; ++i)
		{
			int nx = p.x + dr_x[i];
			int ny = p.y + dr_y[i];

			if (nx < 0 || nx >= N || ny < 0 || ny >= M)
			{
				continue;
			}

			/*
				다음위치가 빈칸이고,
				여분의 벽 개수가 더 적을 때 해당 지점을 방문했었다면

				visit[nx][ny]에 현재 여분 벽 개수 저장
				이동횟수 + 1, 시간 토글 하고 현재 정보를 큐에 push
			*/
			if (map[nx][ny] == '0' && visit[nx][ny] < left)
			{
				visit[nx][ny] = left;
				q.push({ nx, ny, left, dist + 1 , -1 * time });
			}
			/*
				부술 수 있는 벽 개수가 남아있고, 다음위치가 벽이고,
				여분의 벽 개수가 더 적을 때 해당 지점을 방문했었다면

				(낮일 때) visit[nx][ny]에 부수고 난 후 여분 벽 개수 저장
				이동횟수 + 1, 시간 토글하고 현재 정보를 큐에 push
			*/
			else if (left > 0 && map[nx][ny] == '1' && visit[nx][ny] < left - 1)
			{
				// 밤일 때 : 이동 불가
				if (time == NIGHT)
				{
					q.push({ p.x, p.y, left, dist + 1, -1 * time });
				}
				// 낮일 때 : 이동 가능
				else
				{
					visit[nx][ny] = left - 1;
					q.push({ nx, ny, left - 1, dist + 1, -1 * time });
				}
			}
		}
	}

	return -1;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	cin >> N >> M >> K;
	for (int i = 0; i < N; ++i)
	{
		cin >> map[i];
	}

	// map[0][0] ~ map[N - 1][M - 1] 최단 거리 출력 (최대 K개 벽 부수기)
	cout << bfs();

	return 0;
}

 

 

벽 부수고 이동하기 2 문제에서 이동가능한 시간 제약조건이 추가되었다!

마찬가지로 이전 문제의 소스에서 크게 변경한 것은 없으므로,

시간 조건 외의 설명은 벽 부수고 이동하기 문제를 참고 바랍니다

 

 

 

TIP

가장 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다.
이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다.
단, 벽은 낮에만 부술 수 있다.

 

그러니까 시간 제약이 걸린 상황은 앞에 벽을 두고 있을 때라는 얘기다.

이전 버전의 소스에서 시간에 따른 분기를 추가해주면 된다.

밤일 때 -> 큐에 현재 위치를 다시 push한다. (벽을 부술 수 없으므로)

낮일 때 -> 큐에 다음 위치를 push한다.  

 

문제에서 같은 칸에 머물러도 시간이 흐른다 했으니, 이동횟수 추가와 시간 토글은 둘다 해준다.

else if (left > 0 && map[nx][ny] == '1' && visit[nx][ny] < left - 1)
{
	// 밤일 때 : 이동 불가
	if (time == NIGHT)
	{
		q.push({ p.x, p.y, left, dist + 1, -1 * time });
	}
	// 낮일 때 : 이동 가능
	else
	{
		visit[nx][ny] = left - 1;
		q.push({ nx, ny, left - 1, dist + 1, -1 * time });
	}
}

 

 

 

다음 칸이 벽이 아니라 빈칸이라면, 시간에 따라 액션을 달리할 필요가 없다.

큐에 push할 때 시간 상태를 한번 토글해주기만 하면 된다.

/*
	다음위치가 빈칸이고,
	여분의 벽 개수가 더 적을 때 해당 지점을 방문했었다면

	visit[nx][ny]에 현재 여분 벽 개수 저장
	이동횟수 + 1, 시간 토글 하고 현재 정보를 큐에 push
*/
if (map[nx][ny] == '0' && visit[nx][ny] < left)
{
	visit[nx][ny] = left;
	q.push({ nx, ny, left, dist + 1 , -1 * time });
}

 

 

20200615 기준으로 위 풀이는 BOJ에서 가장 빠른 풀이이다 후후 라고 10분전에 글올렸는데 스터디원이 금새 나를 이기셨다 이러기 있기없기ㅜㅜ

벽 부수고 이동하기1 문제에서부터 효율에 대해 고민을 해서 그런지

문제가 변형이 되어도 효율성에 크게 영향을 받지 않았다. 

 

 

주석 없는 코드는 아래로

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

struct pos {
	int x, y;
};

struct info {
	pos p;
	int left, dist, time;
};

int N, M, K;
const int MAX = 1000;
char map[MAX][MAX + 1];
int visit[MAX][MAX];
int dr_x[] = { 0, 1, 0, -1 };
int dr_y[] = { 1, 0, -1, 0 };
enum { NIGHT = -1, DAY = 1 };

int bfs()
{
	memset(visit, -1, sizeof(visit));

	queue<info> q;
	q.push({ 0, 0, K, 1, DAY });

	visit[0][0] = K;

	while (!q.empty())
	{
		pos p = q.front().p;
		int left = q.front().left;
		int dist = q.front().dist;
		int time = q.front().time;
		q.pop();

		if (p.x == N - 1 && p.y == M - 1)
		{
			return dist;
		}

		for (int i = 0; i < 4; ++i)
		{
			int nx = p.x + dr_x[i];
			int ny = p.y + dr_y[i];

			if (nx < 0 || nx >= N || ny < 0 || ny >= M)
			{
				continue;
			}

			if (map[nx][ny] == '0' && visit[nx][ny] < left)
			{
				visit[nx][ny] = left;
				q.push({ nx, ny, left, dist + 1 , -1 * time });
			}
			else if (left > 0 && map[nx][ny] == '1' && visit[nx][ny] < left - 1)
			{
				if (time == NIGHT)
				{
					q.push({ p.x, p.y, left, dist + 1, -1 * time });
				}
				else
				{
					visit[nx][ny] = left - 1;
					q.push({ nx, ny, left - 1, dist + 1, -1 * time });
				}
			}
		}
	}

	return -1;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M >> K;
	for (int i = 0; i < N; ++i)
	{
		cin >> map[i];
	}

	cout << bfs();

	return 0;
}