BOJ 1261 알고스팟

사용한 알고리즘

다익스트라 알고리즘

알고리즘 설명

각 (x,y)좌표로 이루어진 노드 그래프를 구성한다.
경계선을 벗어나지 않는 좌표 상하좌우의 값으로 각 좌표를 연결한다.
위 노드 그래프를 시작점인 (0,0)으로 부터 다익스트라 알고리즘을 적용한다.
(x,y) 좌표를 (x * N + y)로 encoding하여 사용하였다. N값이 100 이하이므로 문제없다. bit-mastking를 사용하는 것이 속도에는 더 빠르다.
dist[M-1,N-1]의 값을 출력한다.

풀이

#include <cstdio>
#include <utility>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,int> P;
const int MAX_N=101;
const int dir[4][2] = { {0,1}, {0,-1}, {1, 0}, {-1, 0} };
const int MAX_INF=1e9;

int N, M, dist[MAX_N*MAX_N];
char board[MAX_N][MAX_N];
bool visited[MAX_N*MAX_N];
vector<P> adj[MAX_N*MAX_N];

inline int encode(int x, int y) {
	return x*N+y;
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i=0; i<M; i++)
		scanf("%s", board[i]);

	// 노드 그래프 구성
	for (int i=0; i<M; i++) {
		for (int j=0; j<N; j++) {
			for (int d=0; d<4; d++) {
				int ni = i + dir[d][0];
				int nj = j + dir[d][1];
				if (ni < 0 || ni >= M || nj < 0 || nj >=N) continue;
				// 상하좌우 연결
				adj[encode(i,j)].push_back(P(encode(ni,nj), board[ni][nj]-'0'));
			}
		}
	}

	// 다익스트라 알고리즘
	priority_queue<P, vector<P>, greater<P> > PQ;
	fill(dist, dist+N*M, MAX_INF);
	dist[0]=0;
	PQ.push(P(0, 0));
	while (!PQ.empty()) {
		int cur_x, cur_y, cur_code;
		do {
			cur_code = PQ.top().second;
			PQ.pop();
		} while (!PQ.empty() && visited[cur_code]);
		if (visited[cur_code]) break;
		visited[cur_code]=true;
		for (int i=0; i<adj[cur_code].size(); i++) {
			int ncode = adj[cur_code][i].first;
			int nw = adj[cur_code][i].second;
			if (dist[ncode] > dist[cur_code] + nw) {
				dist[ncode] = dist[cur_code] + nw;
				PQ.push(P(dist[ncode],ncode));
			}
		}
	}

	printf("%d\n", dist[encode(M-1, N-1)]);
	return 0;
}