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

www.acmicpc.net/problem/4485

4485번: 녹색 옷 입은 애가 젤다지?

다익스트라 알고리즘을 사용한 문제이다.

 

최단거리를 찾아야 하나 가중치가 존재한다.

 

즉 전형적인 다익스트라 알고리즘 문제이다.

 

문제는 지금까지 인접 리스트를 활용해서 풀어보다 보니 이렇게 그래프로 모델링해서 풀어본 적이 없었다.

 

구현 자체는 문제가 없었는데 고민했던 부분은 우선순위 큐에서 우선순위를 어떻게 주어야 하는지였다.

 

내가 사용하고 싶은 것은 dis, x좌표, y좌표 이 3가지였기 때문에 구조체로 만들어 사용하고 싶었다.

 

물론 tuple을 사용해도 되지만(아마 tuple은 greater<tuple>이 있지 않을까 싶네요.. 확실하진 않음)

 

struct(구조체)를 사용하는것이 훨씬 깔끔하기 때문에 구조체를 사용하였다.

 

근데 또 다른 문제는 pq의 인자로 cmp배열을 어떻게 넣느냐였다.

 

greater <struct>는 당연히 말도 안 되고.. 

 

찾아보니 cmp배열을 새롭게 만들어 연산자 오버로딩을 해야 했다.

 

연산자 오버로딩 자체는 어려운 개념이 아니었기 때문에 그대로 수행해서 해결할 수 있었다.

 

struct node {
	int w;
	int x;
	int y;
};

struct cmp {
	bool operator()(node a, node b) {
		return a.w > b.w;
	}
};

//...

priority_queue<node, vector<node>, cmp>pq;

 

 위의 코드에서 우선순위 큐를 선언한 부분을 보면 무슨 이야기인지 알 수 있다.

 

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
 
int n;
int arr[127][127];
int dis[127][127];
bool check[127][127];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
struct node {
    int w;
    int x;
    int y;
};
 
struct cmp {
    bool operator()(node a, node b) {
        return a.w > b.w;
    }
};
 
void dijkstra(int x, int y) {
    priority_queue<node, vector<node>, cmp>pq;
    pq.push(node{ 0,x,y });
    dis[x][y] = arr[x][y];
    while (!pq.empty()) {
        int wei = pq.top().w;
        x = pq.top().x;
        y = pq.top().y;
        pq.pop();
        if (check[x][y]) continue;
        check[x][y] = true;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                if (dis[x][y] + arr[nx][ny] < dis[nx][ny]) {
                    dis[nx][ny] = dis[x][y] + arr[nx][ny];
                    pq.push(node{ dis[nx][ny], nx, ny });
                }
            }
        }
    }
}
 
void init() {
    memset(dis,127, sizeof(dis));
    memset(check, false, sizeof(check));
    memset(arr, 0, sizeof(arr));
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    while (1) {
        cin >> n;
        if (n == 0)break;
        init();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> arr[i][j];
            }
        }
        dijkstra(0, 0);
        cout << "Problem " << t++ << ": " << dis[n - 1][n - 1] << "\n";
    }
}