BOJ 1261 : 알고스팟

#BOJ 1261 : 알고스팟

1261번: 알고스팟

#풀이

문제를 딱 보자마자 BFS문제 유형이여서 행복했지만 일단 다익스트라 알고리즘을 익숙하게 하고 있는 중이라서 다익스트라 알고리즘으로 풀었다.

 

일단 벽이 있는 방은 1 없는 방은 0 이다.

 

이걸 보고 그냥 벽이 있는 방으로 갈 때 비용이 1 인걸로 풀면 되겠다는 생각을 했다.

 

이게 2차원이서 조금 복잡하지만 tuple을 사용해서 비용, x,y로 두고 풀면 쉽게 풀 수 있다.

 

#코드

#include<bits/stdc++.h>

using namespace std;
int n, m;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
const int INF = 300;
int d[101][101];
int arr[101][101];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n>> m;
	
	for(int i = 1; i <= m; i++){
		fill(d[i] + 1, d[i]+1+n, INF);
		for(int j = 1; j <=n; j++){
			char num;
			cin >> num;
			arr[i][j] = num - '0';
		}
	}
	d[1][1] = 0;
	priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<tuple<int,int,int>>>pq;
	pq.push({d[1][1],1,1});
	
	while(!pq.empty()){
		int w, i, j;
		tie(w,i,j) = pq.top(); pq.pop();
		if(w != d[i][j]) continue;
		
		for(int z = 0; z < 4; z++){
			int x = i + dx[z];
			int y = j + dy[z];
			if(x < 1 || y < 1 || x > m || y > n) continue;
			if(w+arr[x][y] >= d[x][y]) continue;
			
			pq.push({w+arr[x][y], x, y});
			d[x][y] = w+arr[x][y];  
		}
	}
	cout << d[m][n] << '\n';
	return 0;
}