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

작성일 | In

문제 링크

  • http://icpc.me/4485

문제 출처

  • 2008 PNRPC D번

사용 알고리즘

  • Dijkstra

풀이

격자 맵의 각 셀을 정점으로 잡고 그래프를 모델링한 뒤, dijkstra를 돌려주면 쉽게 풀 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;

int id[222][222];
vector<p> g[20202];
int arr[222][222];
int n;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void pre() {
	int cnt = 1;
	for(int i=1; i<=125; i++) {
		for(int j=1; j<=125; j++) {
			id[i][j] = cnt++;
		}
	}
}

void init() {
	for(int i=0; i<20202; i++) g[i].clear();
}

int dijkstra() {
	priority_queue<p> pq;
	pq.push({0, 0});
	vector<int> dist(20202, 1e9+7);
	dist[0] = 0;
	while(!pq.empty()) {
		int now = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();
		if(dist[now] < cost) continue;

		for(auto i : g[now]) {
			int nxt = i.first;
			int nxtCost = i.second + cost;
			if(dist[nxt] > nxtCost) {
				pq.push({-nxtCost, nxt});
				dist[nxt] = nxtCost;
			}
		}
	}
	return dist[id[n][n]];
}

void solve(int tc) {
	init();
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			cin >> arr[i][j];
		}
	}

	g[0].push_back({1, arr[1][1]});
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			for(int k=0; k<4; k++) {
				int x = i + dx[k];
				int y = j + dy[k];
				if(x < 1 || y < 1 || x > n || y > n) continue;
				g[id[i][j]].push_back({id[x][y], arr[x][y]});
			}
		}
	}

	cout << "Problem " << tc << ": " << dijkstra() << "\n";
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	pre();
	int cnt = 1;
	while(1) {
		cin >> n;
		if(n) solve(cnt++);
		else break;
	}
}