[백준/C++] 4485번: 녹색 옷 입은 애가 젤다지?
방법
다익스트라로 구현
각 위치에서 방향그래프로 생각
코드
#include<bits/stdc++.h>
#define INF 987654321
using namespace std;
struct info {
int i, j, w;
info() {};
info(int i, int j, int w) :i(i), j(j), w(w) {};
bool operator <(const info i) const {
return w > i.w;
}
};
int N, w, t, f;
bool check[130][130];
vector<info> g[130][130];
int dist[130][130];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
while (true) {
cin >> N;
if (N == 0) break;
t++;
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= N; j++) {
check[i][j] = false;
dist[i][j] = INF;
g[i][j].clear();
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> w;
if (i == 1 && j == 1) { f = w; continue; }
// map[i][j]로 들어오는 방향
g[i][j - 1].push_back(info(i, j, w));
g[i - 1][j].push_back(info(i, j, w));
g[i][j + 1].push_back(info(i, j, w));
g[i + 1][j].push_back(info(i, j, w));
}
}
// 다익스트라
priority_queue<info> pq;
pq.push(info(1, 1, 0));
dist[1][1] = 0;
while (!pq.empty()) {
info cur = pq.top();
pq.pop();
if (check[cur.i][cur.j]) continue;
check[cur.i][cur.j] = true;
for (int z = 0; z < g[cur.i][cur.j].size(); z++) {
int nxt_i = g[cur.i][cur.j][z].i;
int nxt_j = g[cur.i][cur.j][z].j;
int nxt_w = g[cur.i][cur.j][z].w;
if (dist[cur.i][cur.j] + nxt_w < dist[nxt_i][nxt_j]) {
dist[nxt_i][nxt_j] = dist[cur.i][cur.j] + nxt_w;
pq.push(info(nxt_i, nxt_j, dist[nxt_i][nxt_j]));
}
}
}
cout << "Problem " << t << ": " << dist[N][N] + f << "\n";
}
return 0;
}
Author And Source
이 문제에 관하여([백준/C++] 4485번: 녹색 옷 입은 애가 젤다지?), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@0inn/백준C-4485번-녹색-옷-입은-애가-젤다지저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)