백준 1261 알고스팟

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 최단경로를 구하는 문제입니다. 출발점에서 N,M까지 가는데 부숴야 하는 벽의 최소 개수를 구해야 하므로 출발지에서 N,M까지의 최단경로를 구하면 해결 할 수 있습니다. 따라서 다익스트라 알고리즘을 통하여 해결하면 됩니다.

 

노드와 간선으로 정보가 주어지는 것이 아니라 N*M의 판에 대한 정보가 주어지므로 i,j에 위치했을 때는 상 하 좌 우로 이동이 가능하므로 상하좌우 노드와 현재의 노드가 연결 되어 있다고 생각하고 문제를 해결하면 됩니다. 

 

다음은 코드입니다.

 

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

#define INF 987654321
 
int arr[101][101];
priority_queue<pair<int, pair<int, int>> > pq;
int answer[101][101];
int nextx[4] = {0, 1, 0, -1};
int nexty[4] = {1, 0, -1, 0};
int N,M;

void dijkstra() {
	
	answer[1][1] = arr[1][1];
	pq.push(make_pair(-answer[1][1], make_pair(1, 1)));
	while(!pq.empty()) {
		int cost = -pq.top().first;
		int x = pq.top().second.first;
		int y = pq.top().second.second;
		pq.pop();
		
		for(int i = 0; i < 4; i++) {
			int xx = x + nextx[i];
			int yy = y + nexty[i];
			
			if(xx < 1 || xx > N || yy < 1 || yy > M) continue;
			
			int nextDist = cost + arr[xx][yy];
			if(answer[xx][yy] > nextDist) {
				answer[xx][yy] = nextDist;
				pq.push(make_pair(-nextDist, make_pair(xx, yy)));
			}
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> M >> N;
	fill(&answer[0][0], &answer[100][101], INF); 
	for(int i = 1; i <= N; i++) {
		string str; cin >> str;
		for(int j = 1; j <= M; j++) 
				arr[i][j] = str[j-1] - '0';
	}
	dijkstra();
	cout<<answer[N][M];
	
	
	return 0;
}