미로 만들기(0-1 BFS)

백준 2665번

쉽게 말해 (0, 0)에서부터 시작해 (n - 1, n - 1)까지 이동하는데 갈 수 없는 방을 갈 수 있게 만들어 최소한의 방을 바꿔야한다

현재 위치에서 흰 방으로 가려면 그냥 가면 되고 검은 방으로 가려면 그 방을 흰 방으로 바꿔야 한다. 즉 다른 방으로 이동할 때 다른 BFS 문제들은 가중치가 다 똑같이 1이지만 이런 문제같은 경우 가중치가 0(흰 방으로 이동) 또는 1(검은 방으로 이동)이다

일반적인 BFS 탐색과 동일하지만 탐색할 때 가중치가 0인 경로가 존재하기에 큐를 탐색할 때 가중치가 더 낮은 경로부터 탐색해야 한다

다익스트라로 풀 수 있지만 0-1 BFS가 메모리나 시간 면으로 더 효율적임

풀이

0-1 BFS 같은 경우 deque를 사용해서 탐색하다가 가중치가 0인 방(흰 방)은 push_front로, 가중치가 1인 방(검은 방)은 push_back으로 큐에 추가한다

dp 배열을 이용해 dp[i][j]는 (i, j)번째 방까지 최소로 검은 방을 흰 방으로 바꾼 횟수를 저장한다. 최소를 구해야 하니 dp는 최댓값으로 초기화한다

여기선 visited 배열을 이용하지 않고 탐색을 진행하는데 대신 다음 방으로 가는 가중치를 계산해 다음 방의 가중치보다 작다면 업데이트하고 방을 큐에 추가하는 방법이다

코드

#include <bits/stdc++.h>
using namespace std;

int n;
int arr[51][51];
int dp[51][51];

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

void Input()
{
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		string input;
		cin >> input;

		for (int j = 0; j < n; j++)
		{
			arr[i][j] = input[j] - '0';
		}
	}
}

void Solve()
{
	vector<vector<int>> dp(n, vector<int>(n, INT_MAX));

	deque<pair<int, int>> dq;
	dq.push_front({ 0, 0 });
	dp[0][0] = 0;

	while (!dq.empty())
	{
		int y = dq.front().first;
		int x = dq.front().second;
		dq.pop_front();

		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;

			int count = dp[y][x] + (arr[ny][nx] == 0 ? 1 : 0);

			if (count < dp[ny][nx])
			{
				dp[ny][nx] = count;
				if (arr[ny][nx] == 0)
					dq.push_back({ ny, nx });
				else
					dq.push_front({ ny, nx });
			}
		}
	}

	cout << dp[n - 1][n - 1];
}

int main()
{
	Input();

	Solve();
}

회고

처음에는 그냥 BFS로 풀려다가 메모리 초과가 떠서 실패했다

종종 이런 유형의 문제가 자주 봤던 것 같은데 풀이 방법을 기억하면 될 것 같다

비슷한 문제

백준 1261번 : 알고스팟
백준 13549번 : 숨바꼭질 3