반응형
문제링크: https://www.acmicpc.net/problem/4485
4485번: 녹색 옷 입은 애가 젤다지?
젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주
www.acmicpc.net
최단거리를 도출하는 문제입니다.
접근방식
1. 일반적인 bfs 방식과 다익스트라 방식 2가지를 생각함
3. 수의 범위가 125*125로 비교적 작기 때문에 둘다 가능할 것이라고 생각함
결과적으로 둘다 ok! 다익스트라가 4ms bfs가 8ms
4. 전형적인 방식으로 구현하자!
문제풀이
1. 우선 bfs로 구현함
일반적인 bfs 방식으로 구현이 가능
2. 다익스트라 방식은 dist배열을 생성하고 가장 작은 cost값들을 pop하면서 진행
3. 코드가 간결하니 코드를 보고 이해하는게 빠를 듯
아래는 bfs 방식 정답 코드
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int y_ar[4] = { 0,0,-1,1 };
int x_ar[4] = { 1,-1,0,0 };
int n;
int arr[130][130];
int dist[130][130];
void bfs() {
queue <pair<int, int>> pq;
pq.push(make_pair(0, 0));
dist[0][0] = arr[0][0];
while (!pq.empty()) {
int y = pq.front().first;
int x = pq.front().second;
pq.pop();
for (int i = 0; i < 4; i++) {
int ny = y + y_ar[i];
int nx = x + x_ar[i];
if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
if ( dist[ny][nx] > dist[y][x] + arr[ny][nx]) {
dist[ny][nx] = dist[y][x] + arr[ny][nx];
pq.push(make_pair(ny, nx));
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int cnt = 1;
while (1) {
cin >> n;
if (n == 0)
break;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
dist[i][j] = 2000000000;
}
bfs();
cout << "Problem " << cnt++ << ": " << dist[n - 1][n - 1] << "\n";
}
return 0;
}
아래는 다익스트라 알고리즘 방식
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef struct {
int y;
int x;
}p;
int y_ar[4] = { 0,0,-1,1 };
int x_ar[4] = { 1,-1,0,0 };
int n;
int arr[125][125];
int dist[125][125];
void dijkstra() {
priority_queue <pair<int, pair<int, int>>> pq;
pq.push(make_pair(-1 * arr[0][0], make_pair(0, 0)));
dist[0][0] = arr[0][0];
while (!pq.empty()) {
//int cost = pq.top().first * -1;
int y = pq.top().second.first;
int x = pq.top().second.second;
pq.pop();
for (int i = 0; i < 4; i++) {
int ny = y + y_ar[i];
int nx = x + x_ar[i];
int ncost = arr[ny][nx];
if (ny >= 0 && ny < n && nx >= 0 && nx < n) {
int before_v = dist[ny][nx];
int current_v = dist[y][x] + ncost;
if (before_v > current_v) {
dist[ny][nx] = current_v;
pq.push(make_pair(-1 * current_v, make_pair(ny, nx)));
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int cnt = 1;
while (1) {
cin >> n;
if (n == 0)
break;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
dist[i][j] = 2000000000;
}
dijkstra();
cout << "Problem " << cnt++ << ": " << dist[n - 1][n - 1] << "\n";
}
return 0;
}
반응형
'알고리즘 > 다익스트라' 카테고리의 다른 글
| [백준] 9370-미확인 도착지(C++) (0) | 2021.07.26 |
|---|---|
| [백준] 11779-최소비용 구하기2(C++) / 최신 통과 코드 (2) | 2021.07.12 |
| [백준] 1504-특정한 최단 경로(C++) (2) | 2021.05.21 |
| [백준] 1916-최소비용 구하기 (0) | 2020.08.09 |
| [백준] 1753-최단경로 (0) | 2020.07.29 |