BOJ 4485 녹색 옷 입은 애가 젤다지?

사용한 알고리즘

다익스트라

알고리즘 설명

각 (x, y)를 Vertex로 생각한다.
각 Vertex의 상하좌우를 연결하여 그래프를 만든다.
각 Vertex를 연결시, 가중치 값을 다음 Vertex의 값으로 정한다.
이 단방향 연결그래프의 시작점에서 다익스트라 알고리즘을 적용한다.
시작점 (0,0)에서 도착점 (N-1, N-1)까지의 최단거리를 출력한다.

풀이

// baekjoon 4485 yechan
#include <cstdio>
#include <vector>
#include <queue>
#include <utility>
#include <functional>
#include <algorithm>
using namespace std;
const int MAX_N = 125;
const int INF = 1e9;
const int dir[4][2] = {{0,-1}, {0,1}, {-1,0}, {1,0}};
typedef pair<int, int> P;

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

inline void encode(int x, int y, int &code) {
	code = (x<<7) | y;
}

inline void decode(int code, int &x, int &y) {
	x = code>>7;
	y = code & 0b1111111;
}

int Dijkstra(int sx, int sy, int dx, int dy) {
	priority_queue<P, vector<P>, greater<P> > PQ;
	dist[sx][sy]=board[sx][sy];
	int code;
	encode(sx, sy, code);
	PQ.push(P(0,code));

	while (!PQ.empty()) {
		int ccode;
		int cx, cy;
		do {
			ccode = PQ.top().second;
			decode(ccode, cx, cy);
			PQ.pop();
		} while (!PQ.empty() && visited[cx][cy]);
		if (visited[cx][cy]) break;
		visited[cx][cy]=true;
		for (int d=0; d<4; d++) {
			int nx = cx + dir[d][0];
			int ny = cy + dir[d][1];
			int ncode;
			if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
			if (dist[nx][ny] > dist[cx][cy] + board[nx][ny]) {
				dist[nx][ny] = dist[cx][cy] + board[nx][ny];
				encode(nx, ny, ncode);
				PQ.push(P(dist[nx][ny], ncode));
			}
		}
	}

	return (dist[dx][dy] == INF) ? -1 : dist[dx][dy];
}

int main() {
	while (1) {
		cnt++;
		scanf("%d", &N);
		if (!N) break;
		visited = vector<vector<bool> >(N, vector<bool>(N, false));
		adj = vector<vector<P> >(N);
		dist = vector<vector<int> >(N, vector<int>(N, INF));
		for (int i=0; i<N; ++i)
			for (int j=0; j<N; j++)
				scanf("%d", &board[i][j]);
		printf("Problem %d: %d\n", cnt, Dijkstra(0, 0, N-1, N-1));
	}
	return 0;
}