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

개요

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

2206번: 벽 부수고 이동하기

골드급 BFS 문제다.

풀이

처음에는 구조체에 카운터 변수(cnt)와 부실 기회 변수(brk)를 추가해서 그냥 BFS 돌리면 될 줄 알았다.

테스트 케이스는 통과했지만 오답이 나왔다.

문제는 visited 배열에 있었다.

초반에 벽을 부순 경우의 수가 특정 위치에 방문을 먼저 해버리면 그렇지 않은 경우의 수 들은 전부 방문할 수 없게 된다.

하지만 나중에 벽을 부수어야 더 빠른 경우도 있기 때문에, visited를 벽을 부순 경우와 부수지 않은 경우 두 가지로 나누어서 체크해야 했다.

// before
int visited[LIMIT][LIMIT];

// after
int visited[LIMIT][LIMIT][2];

다음과 바꿔 준 후 부순 경우와 안부순 경우의 방문을 따로 체크해 줬고, 결과는 정답!

 

코드

#include<iostream>
#include<queue>
using namespace std;
constexpr int LIMIT = 1002;

struct Block {
	int y;
	int x;
	int cnt;
	int brk;
};
int N, M;
int map[LIMIT][LIMIT];
int visited[LIMIT][LIMIT][2];
int dy[] = { 0,0,-1,+1 };
int dx[] = { -1,+1,0,0 };
int ans;

void BFS() {
	queue<Block> q;
	q.push({ 1,1,0,1 });

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

		if (y<1 || y>N || x<1 || x>M) continue;
		if (visited[y][x][brk]) continue;
		visited[y][x][brk] = 1;
		if (map[y][x] && brk == 0) continue;
		if (map[y][x] && brk > 0) brk--;
		if (y == N && x == M)
		{
			ans = cnt;
			return;
		}

		for (int i = 0; i < 4; i++)
			q.push({ y + dy[i], x + dx[i], cnt, brk });
	}
	ans = -1;
}


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

	BFS();
	cout << ans;
}