[백준 2665] 미로만들기

문제 풀이

 

(1, 1) 시작점에서 (n, n) 도착점에 도착하기 위해서 몇 번의 검은 방을 부셔야 하는지 최소의 횟수를 구하는 문제다.

 

단순히 BFS 알고리즘을 돌리기에는 에러가 있다.

(3, 3) 의 좌표를 보자.

단순히 BFS를 돌리게 되면 (3,3)은 이전의 (2,3)이나 (3,2)로부터 부신 횟수에 + 1을 하여서 2가 될 수 있지만,

그림을 보면 (3,3)도 1번만 부셔서 갈 수 있는 곳이 된다.

 

기존에 방문을 했더라도 더 빠른 경로가 있다면 그 경로로 값을 바꿔주거나 갱신을 시켜줘야 한다는 것이다.

만약 내 앞의 방이 흰방이면, 방문을 했더라도 더 빠른 경로라면 더 빠른 경로로 갱신하고 다시 살펴본다.

만약 내 앞의 방이 검은방이면, 방문을 했더라도 더 빠른 경로라면 더 빠른 경로로 갱신하고 다시 살펴본다.

이미 방문을 했더라도 더 빠른 경로로 계속 갱신하면서 출구를 찾아나간다.

 

단순한 BFS의 프레임에서 벗어난 새로운 방법의 문제였다.

소스 코드

 

#include <iostream>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

const int MAX = 51;
const int INF = 987654321;
const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };

int n;
int board[MAX][MAX];
int visit[MAX][MAX]; // visit[a][b] = c, (a,b) 까지 오는데 검은방을 흰방으로 바꾼 갯수가 c개

// 핵심은 이미 방문한 좌표라도 더 적은 경로가 있다면 재방문하는 것
void bfs()
{
	fill(visit[0], visit[0] + MAX * MAX, INF);
	queue<pair<int, int> > q;
	q.push({ 0,0 });
	visit[0][0] = 0;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
			// 흰방
			if (board[nx][ny] == 1)
			{
				if (visit[nx][ny] > visit[x][y])
				{
					visit[nx][ny] = visit[x][y];
					q.push({ nx,ny });
				}
			}
			// 검은방이면 부수고 지나갈때
			else
			{
				if (visit[nx][ny] > visit[x][y] + 1)
				{
					visit[nx][ny] = visit[x][y] + 1;
					q.push({ nx,ny });
				}
			}
		}
	}
}

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

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		string str;
		cin >> str;
		for (int j = 0; j < str.length(); j++)
		{
			board[i][j] = str[j] - '0';
		}
	}

	bfs();
	cout << visit[n - 1][n - 1] << endl;
	return 0;
}