(백준 / Dijkstra) 녹색 옷 입은놈이 젤다지
문제 요약
- 젤다는 4방향으로 움직인다
- 움직일때마다 해당 공간의 코인을 휙득한다
- 0,0부터 시작해 N-1,N-1 까지 가면서 코인을 최대한 적게 휙득하는 경우의 코인수를 출력하라
솔루션
y, x에서 목적지까지 도달하는데 최소로 휙득하는 코인의 수를 반환하는 함수를 작성하면 됩니다. 그래프와 dfs 완전탐색은 사실 거의 유사하지만 이를 나누면 크게 2가지 방법이 있습니다.
DFS
DFS를 작성할 때 종종 파라미터에 y, x를 넣어주고 인접한 경로를 방문하면서 값을 체크해주는 방식으로 합니다. 하지만 이 문제는 DFS로 풀려면 조건을 상세하게 정의해줘야 합니다. (y, x)에 방문하기 위해서는 네 인접경로 (y,x-1) (y,x+1) (y-1,x) (y+1,x) 로부터 접근해야 하는데, y,x에서 최적의 값을 알아내려면 네 방향을 진행 했을 때의 결과값을 알아야 합니다. 다시말해 무한루프를 돌게 됩니다. 이를 방지하려면 두가지 방법이 있습니다.
- y,x에 도착했을 때 진입했던 경로로는 최적값을 찾지 않게 처리한다.
- y,x에 진입했을 때 최적값을 [y][x][현재비용]으로 산정한다.
이전에 두 가지 방법 모두 해봤던 것 같으니 이번엔 다익스트라로 해보려고 합니다.
Dijstra
다익스트라는 시작 노드로부터 접근할 수 있는 노드들을 탐색하고, 그 중 최적값이 될 수 있는 노드들을 다시 탐색하는 과정을 반복해 하나의 점에서 모든 점까지의 최적값을 산출해낼 수 있습니다. 단, 최적 부분 구조를 기반으로 하기 때문에 가중치에 음수가 있거나 하는 경우는 적용할 수 없습니다. 이 문제는 음수 가중치가 없고, 좌표는 거리가 1인 그래프와 같으므로 다익스트라를 적용할 수 있습니다.
상태공간
시간복잡도
구현 순서
코드
#include <iostream>
#include <queue>
using namespace std;
/*
* N 넓이
* MAP 필드의 값
* dist[Y][X] [1][1]로부터 [Y][X]까지의 거리
* q 탐색할 대상 좌표 중 가장 작은 수를 최우선으로 갖는 priority queue
*/
#define MAX 130
int N, MAP[MAX][MAX] = { 0, }, D[4][2] = { {-1,0}, {0, 1}, {1,0}, {0, -1} };
int dist[MAX][MAX];
typedef struct _coords {
int v;//1,1에서 y,x까지 도달하는 최소값
int y;
int x;
} coords;
struct cmp {
bool operator()(coords& a, coords& b) {
return a.v > b.v;
}
};
priority_queue <coords, vector<coords>, cmp> q;
//(1,1)에서 (N,N)까지 가는데 최소비용을 저장하는 함수
int dijkstra() {
//(1,1)에서 Y,X까지 가는데의 최소값을 dist[Y][X]에 저장
coords init_coords = { MAP[1][1],1,1 };
q.push(init_coords);
while (!q.empty()) {
coords cur = q.top(); q.pop();
int cv = cur.v, cy = cur.y, cx = cur.x;
dist[cy][cx] = cv;
//cout << cur.v << cur.y << cur.x << endl;
//현재 좌표에서 접근할 수 있는 좌표들 확인
for (int d = 0; d < 4; d++) {
int ny = cy + D[d][0], nx = cx + D[d][1];
if (ny < 1 || ny > N || nx < 1 || nx > N) continue;
int nv = cv + MAP[ny][nx];
if (nv >= dist[ny][nx]) continue;
q.push({ nv, ny, nx });
dist[ny][nx] = nv;
}
}
return 0;
}
int main() {
int i, j, num=0;
while (1) {
//!초기화
cin >> N;
if (N == 0) break;
for (i = 1; i <= N; i++) {
for (j = 1; j <= N; j++) {
dist[i][j] = 1e9;
cin >> MAP[i][j];
}
}
dijkstra();
cout << "Problem " << ++num << ": " << dist[N][N] << endl;
}
}
이슈
- 1e9로 나누어 주지 않아 정수 범위를 초과해,,,
- 자바스크립트와 파이썬에 익숙해지는 바람에 그만,,,
Leave a comment