[BOJ] 16933 벽 부수고 이동하기 3 C++

개요

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

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

골드급 BFS 문제다.

풀이

[BOJ] 2206 벽 부수고 이동하기 C++
[BOJ] 14442 벽 부수고 이동하기 2 C++

위 문제에서 이어지는 문제다.

 

낮과 밤, 정지라는 개념이 추가되었다.

visited 배열의 차원을 하나 늘려서 어느 시간에 왔는지를 체크할 수 있도록 해주었다.

벽에 있을 때 밤인 경우 부시는 기회를 감소시키고, 낮에 벽에 왔을 경우에는 감소하지 않고 가만히 있도록 했다.

원래는 일단 큐에 넣고 조건이 안 맞으면 continue를 걸어주는 방식을 활용했었다.

하지만 누군가에게 코드리뷰를 당했고,, 문제가 있음을 알게 되었다. (고맙습니다 c*k*씨)

조건을 확인하지 않고 큐에 무작정 넣을 경우, 메모리와 시간적 손실이 발생한다.

(좌) 후처리, (우) 선처리

생각보다 엄청 차이 났고, 이 차이로 오답이 발생할 수도 있다.

이 외에도 auto 문법, 상태 관련 변수 네이밍 등 많이 배울 수 있었다.

더 열심히 해야겠다.

코드

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
constexpr int N_LIMIT = 1002;
constexpr int B_LIMIT = 11;
constexpr int T_LIMIT = 2;
constexpr int dy[] = { 0,0,-1,+1 };
constexpr int dx[] = { -1,+1,0,0 };

struct Block {
	int y;
	int x;
	int cnt;
	int brk;
	bool time;
};
int N, M, K;
int map[N_LIMIT][N_LIMIT];
bool visited[N_LIMIT][N_LIMIT][B_LIMIT][T_LIMIT];

int ans;

void BFS() {
	queue<Block> q;
	q.push({ 1,1,1,K,true});
	visited[1][1][K][true] = true;

	while (!q.empty())
	{
		auto [y, x, cnt, brk, time] = q.front();
		q.pop();

		if (y == N && x == M)
		{
			ans = cnt;
			return;
		}

		cnt++;
		time = !time;
		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];
			int ry, rx, rb;
			if (map[ny][nx])
			{
				if (brk <= 0) continue;
				if (!time)
				{
					ry = ny;
					rx = nx;
					rb = brk - 1;
				}
				else
				{
					ry = y;
					rx = x;
					rb = brk;
				}
			}
			else
			{
				ry = ny;
				rx = nx;
				rb = brk;
			}
			if (ry<1 || ry>N || rx<1 || rx>M) continue;
			if (visited[ry][rx][rb][time]) continue;
			visited[ry][rx][rb][time] = true;
			q.push({ ry, rx, cnt, rb, time });

		}
	}
	ans = -1;
}

int main()
{
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
			scanf("%1d", &map[i][j]);

	BFS();
	cout << ans;
}