[다익스트라] (백준 4485) 녹색 옷 입은 애가 젤다지?

알고리즘

다익스트라

 

 

[문제 본문]

문제

젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다!

젤다의 전설 시리즈의 주인공, 링크는 지금 도둑루피만 가득한 N x N 크기의 동굴의 제일 왼쪽 위에 있다. [0][0]번 칸이기도 하다. 왜 이런 곳에 들어왔냐고 묻는다면 밖에서 사람들이 자꾸 "젤다의 전설에 나오는 녹색 애가 젤다지?"라고 물어봤기 때문이다. 링크가 녹색 옷을 입은 주인공이고 젤다는 그냥 잡혀있는 공주인데, 게임 타이틀에 젤다가 나와있다고 자꾸 사람들이 이렇게 착각하니까 정신병에 걸릴 위기에 놓인 것이다.

하여튼 젤다...아니 링크는 이 동굴의 반대편 출구, 제일 오른쪽 아래 칸인 [N-1][N-1]까지 이동해야 한다. 동굴의 각 칸마다 도둑루피가 있는데, 이 칸을 지나면 해당 도둑루피의 크기만큼 소지금을 잃게 된다. 링크는 잃는 금액을 최소로 하여 동굴 건너편까지 이동해야 하며, 한 번에 상하좌우 인접한 곳으로 1칸씩 이동할 수 있다.

링크가 잃을 수밖에 없는 최소 금액은 얼마일까?

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 동굴의 크기를 나타내는 정수 N이 주어진다. (2 ≤ N ≤ 125) N = 0인 입력이 주어지면 전체 입력이 종료된다.

이어서 N개의 줄에 걸쳐 동굴의 각 칸에 있는 도둑루피의 크기가 공백으로 구분되어 차례대로 주어진다. 도둑루피의 크기가 k면 이 칸을 지나면 k루피를 잃는다는 뜻이다. 여기서 주어지는 모든 정수는 0 이상 9 이하인 한 자리 수다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 정답을 형식에 맞춰서 출력한다. 형식은 예제 출력을 참고하시오.

제한

예제 입력 1

3
5 5 4
3 9 1
3 2 7
5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5
7
9 0 5 1 1 5 3
4 1 2 1 6 5 3
0 7 6 1 6 8 5
1 1 7 8 3 2 3
9 4 0 7 6 4 1
5 8 3 2 4 8 3
7 4 8 4 8 3 4
0

예제 출력 1

Problem 1: 20
Problem 2: 19
Problem 3: 36

힌트

W3sicHJvYmxlbV9pZCI6IjQ0ODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIxNzlcdWMwYzkgXHVjNjM3IFx1Yzc4NVx1Yzc0MCBcdWM1NjBcdWFjMDAgXHVjODI0XHViMmU0XHVjOWMwPyIsImRlc2NyaXB0aW9uIjoiPHA+XHVjODI0XHViMmU0XHVjNzU4IFx1YzgwNFx1YzEyNCBcdWFjOGNcdWM3ODRcdWM1ZDBcdWMxMWMgXHVkNjU0XHVkM2QwXHVjNzU4IFx1YjJlOFx1YzcwNFx1YjI5NCBcdWI4ZThcdWQ1M2MocnVwZWUpXHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAgXHVhYzA0XHVkNjM5ICYjMzk7XHViM2M0XHViNDUxXHViOGU4XHVkNTNjJiMzOTtcdWI3N2MgXHViZDg4XHViOWFjXHViMjk0IFx1YWM4MFx1YzgxNVx1YzBjOSBcdWI4ZThcdWQ1M2NcdWIzYzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0XHViMzcwLCBcdWM3NzRcdWFjNzggXHVkNjhkXHViNGRkXHVkNTU4XHViYTc0IFx1YzYyNFx1ZDc4OFx1YjgyNCBcdWMxOGNcdWM5YzBcdWQ1NWMgXHViOGU4XHVkNTNjXHVhYzAwIFx1YWMxMFx1YzE4Y1x1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQhPFwvcD5cclxuXHJcbjxwPlx1YzgyNFx1YjJlNFx1Yzc1OCBcdWM4MDRcdWMxMjQgXHVjMmRjXHViOWFjXHVjOTg4XHVjNzU4IFx1YzhmY1x1Yzc3OFx1YWNmNSwgXHViOWMxXHVkMDZjXHViMjk0IFx1YzljMFx1YWUwOCBcdWIzYzRcdWI0NTFcdWI4ZThcdWQ1M2NcdWI5Y2MgXHVhYzAwXHViNGRkXHVkNTVjIE4geCBOIFx1ZDA2Y1x1YWUzMFx1Yzc1OCBcdWIzZDlcdWFkNzRcdWM3NTggXHVjODFjXHVjNzdjIFx1YzY3Y1x1Y2FiZCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMmU0LiBbMF1bMF1cdWJjODggXHVjZTc4XHVjNzc0XHVhZTMwXHViM2M0IFx1ZDU1OFx1YjJlNC4gXHVjNjVjIFx1Yzc3NFx1YjdmMCBcdWFjZjNcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNjU0XHViMGQwXHVhY2UwIFx1YmIzYlx1YjI5NFx1YjJlNFx1YmE3NCBcdWJjMTZcdWM1ZDBcdWMxMWMgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1Yzc5MFx1YWZiOCAmcXVvdDtcdWM4MjRcdWIyZTRcdWM3NTggXHVjODA0XHVjMTI0XHVjNWQwIFx1YjA5OFx1YzYyNFx1YjI5NCBcdWIxNzlcdWMwYzkgXHVjNTYwXHVhYzAwIFx1YzgyNFx1YjJlNFx1YzljMD8mcXVvdDtcdWI3N2NcdWFjZTAgXHViYjNjXHVjNWI0XHViZDI0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC4gXHViOWMxXHVkMDZjXHVhYzAwIFx1YjE3OVx1YzBjOSBcdWM2MzdcdWM3NDQgXHVjNzg1XHVjNzQwIFx1YzhmY1x1Yzc3OFx1YWNmNVx1Yzc3NFx1YWNlMCBcdWM4MjRcdWIyZTRcdWIyOTQgXHVhZGY4XHViMGU1IFx1YzdhMVx1ZDYwMFx1Yzc4OFx1YjI5NCBcdWFjZjVcdWM4ZmNcdWM3NzhcdWIzNzAsIFx1YWM4Y1x1Yzc4NCBcdWQwYzBcdWM3NzRcdWQyYzBcdWM1ZDAgXHVjODI0XHViMmU0XHVhYzAwIFx1YjA5OFx1YzY0MFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWM3OTBcdWFmYjggXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWNjMjlcdWFjMDFcdWQ1NThcdWIyYzhcdWFlNGMgXHVjODE1XHVjMmUwXHViY2QxXHVjNWQwIFx1YWM3OFx1YjliNCBcdWM3MDRcdWFlMzBcdWM1ZDAgXHViMTkzXHVjNzc4IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjNWVjXHVkMmJjIFx1YzgyNFx1YjJlNC4uLlx1YzU0NFx1YjJjOCBcdWI5YzFcdWQwNmNcdWIyOTQgXHVjNzc0IFx1YjNkOVx1YWQ3NFx1Yzc1OCBcdWJjMThcdWIzMDBcdWQzYjggXHVjZDljXHVhZDZjLCBcdWM4MWNcdWM3N2MgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzU0NFx1Yjc5OCBcdWNlNzhcdWM3NzggW04tMV1bTi0xXVx1YWU0Y1x1YzljMCBcdWM3NzRcdWIzZDlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWIzZDlcdWFkNzRcdWM3NTggXHVhYzAxIFx1Y2U3OFx1YjljOFx1YjJlNCBcdWIzYzRcdWI0NTFcdWI4ZThcdWQ1M2NcdWFjMDAgXHVjNzg4XHViMjk0XHViMzcwLCBcdWM3NzQgXHVjZTc4XHVjNzQ0IFx1YzljMFx1YjA5OFx1YmE3NCBcdWQ1NzRcdWIyZjkgXHViM2M0XHViNDUxXHViOGU4XHVkNTNjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjljY1x1ZDA3YyBcdWMxOGNcdWM5YzBcdWFlMDhcdWM3NDQgXHVjNzgzXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViOWMxXHVkMDZjXHViMjk0IFx1Yzc4M1x1YjI5NCBcdWFlMDhcdWM1NjFcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YzVlYyBcdWIzZDlcdWFkNzQgXHVhYzc0XHViMTA4XHVkM2I4XHVhZTRjXHVjOWMwIFx1Yzc3NFx1YjNkOVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWJhNzAsIFx1ZDU1YyBcdWJjODhcdWM1ZDAgXHVjMGMxXHVkNTU4XHVjODhjXHVjNmIwIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWFjZjNcdWM3M2NcdWI4NWMgMVx1Y2U3OFx1YzUyOSBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWMxXHVkMDZjXHVhYzAwIFx1Yzc4M1x1Yzc0NCBcdWMyMThcdWJjMTZcdWM1ZDAgXHVjNWM2XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWFlMDhcdWM1NjFcdWM3NDAgXHVjNWJjXHViOWM4XHVjNzdjXHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNkOVx1YWQ3NFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTI1KSBOID0gMFx1Yzc3OCBcdWM3ODVcdWI4MjVcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTc0IFx1YzgwNFx1Y2NiNCBcdWM3ODVcdWI4MjVcdWM3NzQgXHVjODg1XHViOGNjXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWM1YjRcdWMxMWMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YjNkOVx1YWQ3NFx1Yzc1OCBcdWFjMDEgXHVjZTc4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWIzYzRcdWI0NTFcdWI4ZThcdWQ1M2NcdWM3NTggXHVkMDZjXHVhZTMwXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViM2M0XHViNDUxXHViOGU4XHVkNTNjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCBrXHViYTc0IFx1Yzc3NCBcdWNlNzhcdWM3NDQgXHVjOWMwXHViMDk4XHViYTc0IGtcdWI4ZThcdWQ1M2NcdWI5N2MgXHVjNzgzXHViMjk0XHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC4gXHVjNWVjXHVhZTMwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjMjE4XHViMjk0IDAgXHVjNzc0XHVjMGMxIDkgXHVjNzc0XHVkNTU4XHVjNzc4IFx1ZDU1YyBcdWM3OTBcdWI5YWMgXHVjMjE4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YzgxNVx1YjJmNVx1Yzc0NCBcdWQ2MTVcdWMyZGRcdWM1ZDAgXHViOWRlXHVjZGIwXHVjMTFjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVkNjE1XHVjMmRkXHVjNzQwIFx1YzYwOFx1YzgxYyBcdWNkOWNcdWI4MjVcdWM3NDQgXHVjYzM4XHVhY2UwXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjQ0ODUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJPYnN0YWNsZSBDb3Vyc2UiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgd29ya2luZyBvbiB0aGUgdGVhbSBhc3Npc3Rpbmcgd2l0aCBwcm9ncmFtbWluZyBmb3IgdGhlIE1hcnMgcm92ZXIuIFRvIGNvbnNlcnZlIGVuZXJneSwgdGhlIHJvdmVyIG5lZWRzIHRvIGZpbmQgb3B0aW1hbCBwYXRocyBhY3Jvc3MgdGhlIHJ1Z2dlZCB0ZXJyYWluIHRvIGdldCBmcm9tIGl0cyBzdGFydGluZyBsb2NhdGlvbiB0byBpdHMgZmluYWwgbG9jYXRpb24uIFRoZSBmb2xsb3dpbmcgaXMgdGhlIGZpcnN0IGFwcHJveGltYXRpb24gZm9yIHRoZSBwcm9ibGVtLjxcL3A+XHJcblxyXG48cD5OIHggTiBzcXVhcmUgbWF0cmljZXMgY29udGFpbiB0aGUgZXhwZW5zZXMgZm9yIHRyYXZlcnNpbmcgZWFjaCBpbmRpdmlkdWFsIGNlbGwuIEZvciBlYWNoIG9mIHRoZW0sIHlvdXIgdGFzayBpcyB0byBmaW5kIHRoZSBtaW5pbXVtLWNvc3QgdHJhdmVyc2FsIGZyb20gdGhlIHRvcCBsZWZ0IGNlbGwgWzBdWzBdIHRvIHRoZSBib3R0b20gcmlnaHQgY2VsbCBbTi0xXVtOLTFdLiBMZWdhbCBtb3ZlcyBhcmUgdXAsIGRvd24sIGxlZnQsIGFuZCByaWdodDsgdGhhdCBpcywgZWl0aGVyIHRoZSByb3cgaW5kZXggY2hhbmdlcyBieSBvbmUgb3IgdGhlIGNvbHVtbiBpbmRleCBjaGFuZ2VzIGJ5IG9uZSwgYnV0IG5vdCBib3RoLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+RWFjaCBwcm9ibGVtIGlzIHNwZWNpZmllZCBieSBhIHNpbmdsZSBpbnRlZ2VyIGJldHdlZW4gMiBhbmQgMTI1IGdpdmluZyB0aGUgbnVtYmVyIG9mIHJvd3MgYW5kIGNvbHVtbnMgaW4gdGhlIE4geCBOIHNxdWFyZSBtYXRyaXguIFRoZSBmaWxlIGlzIHRlcm1pbmF0ZWQgYnkgdGhlIGNhc2UgTiA9IDAuPFwvcD5cclxuXHJcbjxwPkZvbGxvd2luZyB0aGUgc3BlY2lmaWNhdGlvbiBvZiBOIHlvdSB3aWxsIGZpbmQgTiBsaW5lcywgZWFjaCBjb250YWluaW5nIE4gbnVtYmVycy4gVGhlc2UgbnVtYmVycyB3aWxsIGJlIGdpdmVuIGFzIHNpbmdsZSBkaWdpdHMsIHplcm8gdGhyb3VnaCBuaW5lLCBzZXBhcmF0ZWQgYnkgc2luZ2xlIGJsYW5rcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5FYWNoIHByb2JsZW0gc2V0IHdpbGwgYmUgbnVtYmVyZWQgKGJlZ2lubmluZyBhdCBvbmUpIGFuZCB3aWxsIGdlbmVyYXRlIGEgc2luZ2xlIGxpbmUgZ2l2aW5nIHRoZSBwcm9ibGVtIHNldCBhbmQgdGhlIGV4cGVuc2Ugb2YgdGhlIG1pbmltdW0tY29zdCBwYXRoIGZyb20gdGhlIHRvcCBsZWZ0IHRvIHRoZSBib3R0b20gcmlnaHQgY29ybmVyLCBleGFjdGx5IGFzIHNob3duIGluIHRoZSBzYW1wbGUgb3V0cHV0ICh3aXRoIG9ubHkgYSBzaW5nbGUgc3BhY2UgYWZ0ZXIgJmxkcXVvO1Byb2JsZW0mcmRxdW87IGFuZCBhZnRlciB0aGUgY29sb24pLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

 

[푼 코드]

#include <iostream>
#include <queue>
#define MAXNUM 126
#define INF 987654321
using namespace std;
int N;
int arr[MAXNUM][MAXNUM];
int d[MAXNUM][MAXNUM];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
bool IsRange(int x, int y)
{
	return (x >= 0 && x < N&& y >= 0 && y < N);
}

int Solved(int x,int y)
{
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			d[y][x] = INF;
		}
	}
	d[y][x] = arr[y][x];

	priority_queue<pair<int, pair<int, int>>> pq;
	pq.push({ -d[y][x], { x,y } });
	while (!pq.empty())
	{
		int cost = -pq.top().first;
		int posX = pq.top().second.first;
		int posY = pq.top().second.second;
		pq.pop();
		for (int i = 0; i < 4; i++)
		{
			int tempX = posX + dx[i];
			int tempY = posY + dy[i];
			if (IsRange(tempX, tempY))
			{
				if (d[tempY][tempX] > d[posY][posX] + arr[tempY][tempX])
				{
					d[tempY][tempX] = d[posY][posX] + arr[tempY][tempX];
					pq.push({ -d[tempY][tempX], { tempX,tempY } });
				}
			}
		}
	}

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie();
	cout.tie();
	int countNum = 1;
	while (1)
	{
		cin >> N;
		if (N == 0)
			break;

		for (int y = 0; y < N; y++)
		{
			for (int x = 0; x < N; x++)
			{
				cin >> arr[y][x];
			}
		}
		cout << "Problem " <<countNum++<<": " << Solved(0, 0) << '\n';
	}
	return 0;
}

 

 

#다익스트라 #백준4485 #알고리즘 #최단경로알고리즘 #백준