[백준 2665] 미로만들기 (C++)

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

문제

---

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

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

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

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

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

 

입력

---

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

 

출력

---

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

 

문제 풀이

---

다익스트라 문제.

 

이전에 지나간 검은 방의 수에 따라 특정 칸에 도달했을 때의 지나는 검은 방의 수가 달라지기 때문에 다익스트라를 활용하여 칸들을 탐색한다. 각 칸마다 이전에 지난 최소 검은 방의 수보다 현재 탐색했을 때 방각 칸에서 지나는 검은 방의 수가 더 적다면 해당 칸을 업데이트한다.

 

아래는 코드.

#include <iostream>
#include <queue>
#define MAX 123456789
using namespace std;

int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};
int** arr;
int** minCount;
int N;

struct info
{
	int x;
	int y;
	int changeCount;
	info(int a, int b, int c)
	{
		x = a;
		y = b;
		changeCount = c;
	}
};

struct cmp
{
	bool operator()(info& i1, info& i2)
	{
		if (i1.changeCount < i2.changeCount)
		{
			return false;
		}
		else if (i1.changeCount == i2.changeCount)
		{
			if (i1.x > i2.x)
			{
				return false;
			}
			else if (i1.x == i2.x)
			{
				return i1.y < i2.y;
			}
			else
			{
				return true;
			}
		}
		else
		{
			return true;
		}
	}
};

priority_queue<info, vector<info>, cmp> pq;

void dijkstra()
{

	pq.push(info(0, 0, 0));
	minCount[0][0] = 0;
	while (!pq.empty())
	{
		info top = pq.top();
		pq.pop();
		if (top.changeCount > minCount[top.x][top.y])
		{
			continue;
		}
		for (int i = 0; i < 4; i++)
		{
			int nextX = top.x + dx[i];
			int nextY = top.y + dy[i];
			if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N)
			{
				if (arr[nextX][nextY] == 1 && top.changeCount < minCount[nextX][nextY])
				{
					pq.push(info(nextX, nextY, top.changeCount));
					minCount[nextX][nextY] = top.changeCount;
				}
				else if (arr[nextX][nextY]==0 && top.changeCount+1 < minCount[nextX][nextY])
				{
					pq.push(info(nextX, nextY, top.changeCount+1));
					minCount[nextX][nextY] = top.changeCount+1;
				}
			}
		}
	}
	cout << minCount[N - 1][N - 1] << "\n";
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	char c;
	cin >> N;
	arr = new int*[N];
	minCount = new int*[N];
	for (int i = 0; i < N; i++)
	{
		arr[i] = new int[N];
		minCount[i] = new int[N];
		for (int j = 0; j < N; j++)
		{
			cin >> c;
			arr[i][j] = c - 48;
			minCount[i][j] = MAX;
		}
	}
	dijkstra();
	return 0;
}