C++ / 1261 / 알고스팟 ( 데이크스트라 )

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

문제 요약

알고스팟 운영진이 모두 미로에 갇혔습니다.

미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없습니다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 합니다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방입니다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 입니다. 단, 미로의 밖으로 이동 할 수는 없습니다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있습니다. 벽을 부수면, 빈 방과 동일한 방으로 변합니다.

만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는Baejoon Online judge에 수록되어 있기 때문에, sudo를 사용할 수 없습니다.

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성해야합니다.

문제 풀이

1. 미로를 입력받습니다.

2. dist 배열을 초기화 해주고 데이크스트라 탐색을 해줍니다.

3. n * m 2 차원 배열이기 때문에 pq도 {cost, { y, x } } 형태로 만들어줍니다.

4.  시작 노드의 코스트는 0입니다.

5. 4방향으로 탐색 해주는데 탐색 노드가 범위 안에 있을 경우 과거 코스트와 현재 노드의 비용 ( 벽이면 1 아니면 0 )을 합해서 현재 노드의 코스트보다 작으면 갱신해줍니다. 

6. 탐색을 마치고 목적지의 최소 벽의 개수를 출력합니다.

주의할 점

2차원 배열에서 데이크스트라 탐색에 주의합시다.목적지데 도달하기 위한 최소 비용 입니다.

코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

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



int n, m;
vector<vector<int>>v;
int dist[104][104];
void dijkstra(int y, int x)
{
	//{ cost { y, x }} 형태
	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
	pq.push({ 0, {y, x} });
	dist[y][x] = 0;
	while (!pq.empty())
	{
		int y = pq.top().second.first;
		int x = pq.top().second.second;
		int cost = pq.top().first;
		pq.pop();
		if (dist[y][x] < cost)
		{
			continue;
		}

		for (int i = 0; i < 4; i++)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= m || ny < 0 || nx >= n || nx < 0)
			{
				continue;
			}
			// 벽 개수 더함
			int nextcost = v[ny][nx] + cost;

			// 기존 값 보다 작으면
			if (dist[ny][nx] > nextcost)
			{
				dist[ny][nx] = nextcost;
				// 다음탐색
				pq.push({ nextcost, {ny, nx} });
			}
		}

	}

}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	v.resize(m, vector<int>(n));

	for (int i = 0; i < m; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < n; j++)
		{
			v[i][j] = s[j] - '0';
		}
	}


	// dist 초기화
	fill(&dist[0][0], &dist[m + 1][n + 1], 1e9);
	dijkstra(0, 0);
	cout << dist[m - 1][n - 1];
	return 0;
}

예제1

3 3
011
111
110

결과1

예제2

4 2
0001
1000

결과2

예제3

6 6
001111
010000
001111
110001
011010
100010

결과3