[BOJ] 2665번 미로만들기

문제

n×n 바둑판 모양으로 총 n²개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어가 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.

시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.

아래 그림은 n=8인 경우의 한 예이다.

위 그림에서는 두 개의 검은 방(예를 들어 (4,4)의 방과 (7,8)의 방)을 흰 방으로 바꾸면, 시작방에서 끝방으로 갈 수 있지만, 어느 검은 방 하나만을 흰 방으로 바꾸어서는 불가능하다. 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오.

단, 검은 방을 하나도 흰방으로 바꾸지 않아도 되는 경우는 0이 답이다.

입력

첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.

출력

첫 줄에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 출력한다.

예제

// 입력
8
11100110
11010010
10011010
11101100
01000111
00110001
11011000
11000111

// 출력
2

코드

// cpp 17

// 이 문제를 푸는 방법은 2가지가 있다.
// 먼저, 다익스트라 알고리즘을 이용하는 방법이다.
// 다익스트라 알고리즘를 모른다면 맨 밑의 링크를 참고하길 바란다.
#include <iostream>
#include <string>
#include <utility>
#include <functional>
#include <queue>

using namespace std;

using pos = pair<int, int>;
using pqelem = pair<pos, int>;

int N, dist[50][50];
int dr[] = { -1, 1, 0, 0 }, dc[] = { 0, 0, -1, 1 };
int map[50][50];
priority_queue<pqelem> pq;

int main()
{
	scanf("%d", &N);
	for (int r = 0; r < N; r++)
	{
		for (int c = 0; c < N; c++)
		{
			scanf("%1d", &map[r][c]);
			// 각각의 방들을 vertex라고 하면, 각 값들은 weight라고 볼 수 있다.
			// 해당 문제는 흰 방을 1, 검은 방을 0으로 준다.
			// 원하는 방향으로 동작시키려면 이 값을 반전시켜야 한다.
			map[r][c] = (map[r][c] == 0) ? 1 : 0;
			dist[r][c] = 987654321;
		}
	}
	dist[0][0] = 0;

	pq.push({ {0, 0}, 0 });
	while (!pq.empty())
	{
		// std::priority_queue의 기본 정렬은 내림차순이다. (<)
		// 기본적으로 끝점 방향으로 나아가야 하기 때문에
		// 오른쪽 혹은 아래쪽으로 나아가야 한다.
		int r = pq.top().first.first;
		int c = pq.top().first.second;
		int dis = -pq.top().second; // 이 값은 추후 설명한다.
		pq.pop();

		// dis가 현재 저장되어 있는 값보다 크다면
		// 확인할 필요가 없다.
		if (dis > dist[r][c])
			continue;

		// 상하좌우를 탐색한다.
		for (int i = 0; i < 4; i++)
		{
			int nr = r + dr[i];
			int nc = c + dc[i];

			if (nr < 0 || nr >= N || nc < 0 || nc >= N)
				continue;

			// 새 값이 더 작다면 갱신시켜야 한다.
			int newDis = dis + map[nr][nc];
			if (newDis < dist[nr][nc])
			{
				dist[nr][nc] = newDis;
				// 여기서 음수로 값을 저장하는 이유는
				// 검은방을 택하기 보단 흰방을 택하기 위해서이다.
				pq.push({ { nr, nc }, -newDis });
			}
		}
	}

	cout << dist[N - 1][N - 1];
}

// 두번째 방법은 DFS를 할때마다 갱신시키는 것이다.
#include <iostream>
#include <string>

using namespace std;

string map[50];
int N, cnt;
int dr[] = { -1, 1, 0, 0 }, dc[] = { 0, 0, -1, 1 };
bool hasEnded, isVisited[50][50];

void dfs(int r, int c)
{
	// 목표에 도달했다면 더이상 DFS를 하지 않는다.
	if (r == N - 1 && c == N - 1)
	{
		hasEnded = true;
		return;
	}

	isVisited[r][c] = true;

	for (int i = 0; i < 4; i++)
	{
		int nr = r + dr[i];
		int nc = c + dc[i];

		if (nr < 0 || nr >= N || nc < 0 || nc >= N)
			continue;

		if (map[nr][nc] == '1' && !isVisited[nr][nc])
			dfs(nr, nc);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> map[i];

	while (true)
	{
		dfs(0, 0);
		if (hasEnded)
			break;

		++cnt;
		for (int r = 0; r < N; r++)
		{
			for (int c = 0; c < N; c++)
			{
				// 방문한 흰 방들 중 주변의 검은방을 뚫는다.
				if (map[r][c] == '1' && isVisited[r][c])
				{
					for (int i = 0; i < 4; i++)
					{
						int nr = r + dr[i];
						int nc = c + dc[i];

						if (nr < 0 || nr >= N || nc < 0 || nc >= N)
							continue;

						if (map[nr][nc] == '0')
							map[nr][nc] = '1';
					}
				}
			}
		}

		memset(isVisited, false, sizeof(isVisited));
	}

	cout << cnt;
}