백준 4485번 녹색 옷 입은 애가 젤다지?

문제링크

문제 해설

접근법

문제 설명은 뭐라뭐라하는데 결국 중요한건 출발부터 도착까지 최소 비용으로 가고 싶은 것이다.

출발 - 도착, 최소 비용? 지난번에 풀이한 최소 비용 구하기와 동일한 다익스트라이다.

조금 다른 것이라면 이번에는 모든 노드가 연결되어 있다는 것뿐이다.

풀이

다익스트라 알고리즘을 이용하자.

1. 우선순위 큐를 사용한다.

• 우선순위 큐에는 (비용, 노드번호)를 넣는다.
• 처음에는 당연히 {(0,0)의 도둑루피, (0,0)}을 넣는다. (0,0)가 출발점이기 때문이다.
• 해당칸까지의 비용을 담은 배열을 dist라 하자.

2 .우선순위 큐 push/pop

• 큐에 들어 있는 것을 pop한다. pop한 칸의 네 방향을 살펴본다.
• 네 방향 중 동굴을 벗어나지 않으면서 더 적은 비용으로 해당 칸을 갈 수 있다면 비용을 수정하고 해당칸까지의 비용과 해당 칸을 우선순위 큐에 넣어준다. (다익스트라 알고리즘)
• 결국 답은 dist[n-1][n-1]이 될 것이다.

3. 형식에 맞게 출력
사실 이게 제일 중요하다….. 왜냐하면 똑같은 코드였지만 빈칸 출력 하나 차이로 계속 틀렸기 때문이다.

소스코드

#include <iostream>
#include <queue>
#include <cstring>
#include <string>
// 백준 4485 녹색 옷 입은 애가 젤다지?

using namespace std;

// 노드간 최소비용? => 다익스트라.

typedef pair<int, vector<int>> pi;
const int INF = 987654321;
vector<int> ans;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0, -1,1 };

int dji(vector<vector<int>> board, int n) {
	priority_queue<pi, vector<pi>, greater<pi>> pq;

	vector<vector<int>> dist(n, vector<int>(n, INF));

	pq.push({ board[0][0],{0,0} });
	dist[0][0] = board[0][0];

	while (!pq.empty()) {
		int cost = pq.top().first;
		int x = pq.top().second[0], y = pq.top().second[1];
		pq.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= n)
				continue;
			if (dist[nx][ny] > cost + board[nx][ny]) {
				dist[nx][ny] = cost + board[nx][ny];
				pq.push({ dist[nx][ny], {nx,ny} });
			}
		}
	}
	return dist[n - 1][n - 1];
}


int main() {
	int tc = 0;
	while (true) {
		tc++;
		int n;
		cin >> n;
		if (n == 0)
			return 0;
		vector<vector<int>> board(n, vector<int>(n));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> board[i][j];
			}
		}
		cout << "Problem "<<tc<< ": " << dji(board, n) << endl;
	}
	return 0;
}