백준 Gold 4 알고스팟

알고스팟 (백준 Gold 4)

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

장애물이 주어지는 최단 경로 찾기 문제이다
요점은 ‘최소한’의 벽을 부수면서 지나가는 것

따라서 priority_queue의 조건을 ‘가장 벽을 적게 부신 상태’로
잡으면 충분히 해결 가능한 문제였다

풀이 방식

• 노드 방문용 구조체 info 를 만들어
  현재 좌표 와 ‘벽을 부순 갯수’를 등록
  

• 현재 좌표까지 오는데 ‘부순 벽의 최소 개수’를
  기록하는 배열 dp 생성
  (어떤 의미에선 최선 값이기도 하니)
  

• 이후 priority_queue의 조건을
  ‘벽을 부순 개수’가 작은 것을
  우선하도록 하며 탐색 진행
  

• 다음 방문지가 빈방(0)이라면
  cost는 증가시키지 않음
  그렇지 않다면 1증가
  

• 도착지에 도달 시 종료
  

결과

제출 코드

#include<iostream>
#include<vector>
#include<queue>
#include<limits.h>
#include<string>

using namespace std;

const int dirY[4] = { -1,0,1,0 };
const int dirX[4] = { 0,1,0,-1 };

struct info
{
	int nowY, nowX;
	int nowCost;
};

struct Compare
{
	bool operator()(const info& a, const info& b) const
	{
		return a.nowCost > b.nowCost;
	}
};

int best(vector<vector<int>>& miro)
{
	int n = miro.size();
	int m = miro[0].size();

	vector<vector<int>> dp(n, vector<int>(m, INT_MAX));

	priority_queue<info, vector<info>, Compare> pq;
	pq.push({ 0,0,0 });

	while (pq.empty() == false)
	{
		int nowY = pq.top().nowY;
		int nowX = pq.top().nowX;
		int nowCost = pq.top().nowCost;
		pq.pop();

		if (dp[nowY][nowX] <= nowCost)
			continue;

		dp[nowY][nowX] = nowCost;

		if (nowY == n - 1 && nowX == m - 1)
			break;

		for (int i = 0; i < 4; i++)
		{
			int nextY = nowY + dirY[i];
			int nextX = nowX + dirX[i];

			if (nextY < 0 || nextX < 0 ||
				nextY >= n || nextX >= m)
				continue;

			if (miro[nextY][nextX] == 0)
				pq.push({ nextY,nextX,nowCost });
			else
				pq.push({ nextY,nextX,nowCost + 1 });

		}
	}

	return dp[n - 1][m - 1];
}


int main()
{
	int m, n;
	cin >> m >> n;

	vector<vector<int>> miro(n, vector<int>(m, -1));

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

	cout << best(miro);

	return 0;
}