[백준 C++] 1261 알고스팟 - 다익스트라

---

문제풀이

 

다익스트라 알고리즘을 이용해서 푸는 문제입니다.

(1,1) -> (n,m)으로 이동하되, 인접 노드 탐색 시 priority_queue(최소힙) 자료구조를 이용해서

큐에 들어오는 노드 중 벽을 부수는 비용이 가장 적은 노드부터 탐색하도록 했습니다.

그리고 인접 노드의 최소비용 배열의 값을 갱신해주도록 해서 풀었습니다.

---

코드

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

typedef pair<int, int> p;
typedef pair<int, p> pp;

const int Inf = INT_MAX;
const int DX[4] = { -1, 0, 1, 0 };
const int DY[4] = { 0, -1, 0, 1 };

int N, M;
bool IsWall[100][100];
int Cost[100][100];

void Dijkstra()
{
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			Cost[i][j] = Inf;
		}
	}

	priority_queue<pp, vector<pp>, greater<pp>> PQ;
	Cost[0][0] = 0;
	PQ.emplace(0, p(0, 0));
	while (!PQ.empty())
	{
		int Cst = PQ.top().first;
		int R = PQ.top().second.first;
		int C = PQ.top().second.second;
		PQ.pop();
		if (Cst > Cost[R][C])
		{
			continue;
		}

		for (int i = 0; i < 4; ++i)
		{
			int NR = R + DY[i];
			int NC = C + DX[i];
			if (NR < 0 || NR > N - 1 || NC < 0 || NC > M - 1)
			{
				continue;
			}

			int NCst = Cst + ((IsWall[NR][NC]) ? 1 : 0);
			if (NCst < Cost[NR][NC])
			{
				Cost[NR][NC] = NCst;
				PQ.emplace(NCst, p(NR, NC));
			}
		}
	}
}

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

	cin >> M >> N;
	for (int i = 0; i < N; ++i)
	{
		string Line;
		cin >> Line;
		for (int j = 0; j < M; ++j)
		{
			IsWall[i][j] = Line[j] - '0';
		}
	}

	Dijkstra();
	cout << Cost[N - 1][M - 1];
}