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

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

www.acmicpc.net/problem/4485

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

---

 

풀이)

다익스트라 알고리즘을 통해 (0,0) 부터 (N-1,N-1)까지 최소한의 검정루피를 얻는 경로를 구해주면된다.

 

시간복잡도)

시간복잡도는 최악의 경우 모든 x,y좌표를 큐에 넣고 연산하는 작업을 해야하므로 O(N*N) 이 된다.

 

코드)

 

#include <iostream>
#include<queue>
#define MAX 987654321
using namespace std;

int n;
int arr[126][126];
int dist[126][126];
int mv[4][2] = { {1,0},{-1,0},{0,-1},{0,1} };

void input() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
		}
	}
}

int solve() {
	priority_queue<pair<int,pair<int, int>>> q;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dist[i][j] = MAX;
		}
	}
	dist[0][0] = arr[0][0];

	q.push({ -dist[0][0],{0,0} });
	while (!q.empty()) {
		int x = q.top().second.first;
		int y = q.top().second.second;
		int distance = -q.top().first;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + mv[i][0];
			int ny = y + mv[i][1];

			if (nx >= 0 && nx < n&&ny >= 0 && ny < n) {
				if (dist[nx][ny] > distance + arr[nx][ny]) {
					q.push({ -(distance + arr[nx][ny]),{nx,ny} });
					dist[nx][ny] = distance + arr[nx][ny];
				}
			}
		}
	}
	return dist[n-1][n-1];
}

int main(){
	int i = 1;
	while (true) {
		cin >> n;
		if (n == 0) break;


		input();
		int result=solve();
		cout << "Problem " << i++ << ": " << result << "\n";
	}
	return 0;
}