[백준 1261] 알고스팟

https://acmicpc.net/problem/1261

 

---

해설

이 문제는 일반적으로 BFS 나 다익스트라로 풀 것이다.

나는 bfs로 풀면 코드가 복잡해질 것 같아 다익스트라 알고리즘으로 푸는 쪽을 선택했다.

 

다익스트라로 푸는 방법은 간단했다. (사실 간단하진 않다.)

문제에서 나와있듯이 빈 방은 가중치를 0으로, 벽은 가중치를 1로 잡고 다익스트라로 돌려주었다.

 

 

 

˙˙˙

소스코드

 

#include <iostream>
#include <queue>
using namespace std;
const int SIZE = 100;
int M, N;
int map[SIZE][SIZE];
int minCheck[SIZE][SIZE];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
using p =  pair<int, int>;
int INF = 10000;
int main(){
	cin >> M >> N;
	for (int i = 0; i < N; i++) {
		string a; cin >> a;
		for (int j = 0; j < M; j++) {
			int k = a[j] - '0';
			map[i][j] = k;
			minCheck[i][j] = INF;
		}
	}
	queue <p> pq;
	pq.push({ 0, 0 });
	minCheck[0][0] = 0;
	while (!pq.empty()) {
		int x = pq.front().first;
		int y = pq.front().second;
		pq.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < M && ny < N && nx >= 0 && ny >= 0) {
				if (minCheck[ny][nx] > minCheck[y][x] + map[ny][nx]) {
					minCheck[ny][nx] = minCheck[y][x] + map[ny][nx];
					pq.push(p(nx, ny));
				}
			}
		}
	}
	cout << minCheck[N - 1][M - 1] << '\n';
}

 

시간되면 다른 방법으로도 풀어보길 바란다.