[백준] 1261번: 알고스팟

1261번: 알고스팟

 

벽을 가장 적게 부수는 경우의 수를 찾아야 하기때문에 이동하는 방향에 따라서 방문한 곳을 재 방문해야하는 경우가 생긴다. 그래서 priority_queue를 이용해서 가장 적게 부순 경우를 먼저 처리해주어 똑같은 곳을 재방문 하는 경우가 없도록 했다.

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define MAX 101
using namespace std;

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

int n, m;
int map[MAX][MAX];
int visit[MAX][MAX];

int solution(int a,int b) {

	priority_queue<pair<int, pair<int, int>>>pq;
	pq.push({ 0, { a,b} });
	visit[a][b] = 1;

	while (!pq.empty()) {
		int y = pq.top().second.first;
		int x = pq.top().second.second;
		int w = -pq.top().first;
		pq.pop();

		if (y == n && x == m) {
			return w;
		}

		for (int i = 0;i < 4;i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny<1 || nx<1 || ny>n | nx>m) continue;
			if (visit[ny][nx]) continue;

			visit[ny][nx] = true;

			if (map[ny][nx] == 1) pq.push({ -(w + 1),{ny,nx} });
			if (map[ny][nx] == 0) pq.push({ -(w),{ny,nx} });
		}
	}
}


int main() {
	cin >> m >> n;
	
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= m;j++) {
			char c;
			cin >> c;
			map[i][j] = c - '0';
		}
	}
	cout<<solution(1, 1);
}