[백준][4485][c++] 녹색 옷 입은 애가 젤다지?

녹색 옷 입은 애가 젤다지? 문제 링크

[문제 풀이]

좌표와 좌표 사이에 0부터 9라는 가중치가 있는 거라고 볼 수 있으니 흔한 BFS 알고리즘으로 풀 수 없다. 양의 정수 가중치를 가진 최단 거리를 풀 수 있는 다익스트라로 풀 수 있을 것이다. 대신 좌표가 노드가 되고 각 동굴의 크기가 그 노드로 가는 모든 가중치 값으로 봐야 한다.

[내 풀이]

#include <iostream>
#include <string>
#include <cstring>
#include <queue>
#define N_MAX 126

using namespace std;

int N;
int edge[N_MAX][N_MAX];
int vertex[N_MAX][N_MAX];

int dir_y[] = { 1,-1,0,0 };
int dir_x[] = { 0,0,1,-1 };


int dijkstra() {
	vertex[0][0] = edge[0][0];
	priority_queue<pair<int, pair<int,int>>> q;

	q.push(make_pair(-edge[0][0], make_pair(0,0)));

	while (!q.empty()) {
		pair<int, pair<int, int>> cur = q.top();
		q.pop();

		pair<int, int> current = cur.second;
		int dist = -cur.first;
		//if (dist > vertex[current.first][current.second]) continue;

		for (int dir = 0; dir < 4; dir++) {
			int new_y = current.first + dir_y[dir];
			int new_x = current.second + dir_x[dir];
			if (new_y < 0 || new_y >= N || new_x < 0 || new_x >= N) continue;
			int next_dist = edge[new_y][new_x];
			if (dist + next_dist < vertex[new_y][new_x]) {
				vertex[new_y][new_x] = dist + next_dist;
				q.push(make_pair( -vertex[new_y][new_x], make_pair(new_y, new_x)));
			}
		}
	}

	return vertex[N - 1][N - 1];
}

int main() {
	int prob = 0;
	while (1) {
		cin >> N;
		if (N == 0) break;

		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				cin >> edge[y][x];
				vertex[y][x] = 987654321;
			}
		}

		int answer = dijkstra();
		prob++;

		string str = "Problem " + to_string(prob) + ": " + to_string(answer);
		cout << str << "\n";
	}
}

[총평]
노드와 엣지를 잘 정의하면 쉽게 풀리는 문제인 것 같다. 브루트 포스로 푸는 방법도 있던데 참고자료에 넣었다.

[참고자료]
https://yabmoons.tistory.com/388