[C/C++] 프로젝트 오일러 #83 Path sum: four ways(다익스트라)

#83 문제는 난이도 25%로 설정되어 있습니다.  동적 계획법 등으로는 구현하기 어렵고, 다익스트라 알고리즘을 사용해야 합니다.

다익스트라 알고리즘 자체는 너비 우선 탐색, 프림 알고리즘과 비슷한 구현 방법으로 큐 자료구조와 우선순위 큐 자료구조의 이해가 필요합니다.

 

four ways

 

https://projecteuler.net/problem=83

 

다익스트라 알고리즘 구현은 그래프에서 경로 찾기에서 자주 나옵니다.

https://sdev.tistory.com/119

다익스트라 알고리즘

https://sdev.tistory.com/635

#1445 일요일 아침의 데이트

 

제가 작성한 소스입니다.

#include <cstdio>
#include <queue>
using namespace std;

#define    FILENAME    "p083_matrix.txt"
#define    INFTY        1000000000

struct qnode
{
    int sum, row, col;
    qnode(int s, int r, int c) : sum(s), row(r), col(c) { }
    bool operator<(const qnode node) const { return sum > node.sum; }
};

int solve1(int d[][80])
{
    priority_queue<qnode> queue;
    static int v[80][80];
    static char visited[80][80];

    for(int i=0; i<80; i++) for(int j=0; j<80; j++) v[i][j] = INFTY;
    v[0][0] = d[0][0];
    queue.push(qnode(d[0][0], 0, 0));

    for(;;)
    {
        qnode node = queue.top(); queue.pop();
        if(visited[node.row][node.col]) continue;
        if(node.row == 79 && node.col == 79 ) return node.sum;
        visited[node.row][node.col] = 1;
        
        const int off[4][2] = { 0, 1, 1, 0, 0, -1, -1, 0 };
        for( int i = 0 ; i < 4 ; i++ )
        {
            int nrow = node.row + off[i][0];
            int ncol = node.col + off[i][1];
            if( nrow < 0 || ncol < 0 || nrow >= 80 || ncol >= 80 ) continue;
            if( visited[nrow][ncol] ) continue;
            int nsum = node.sum + d[nrow][ncol];
            if(nsum < v[nrow][ncol])
            {
                v[nrow][ncol] = nsum;
                queue.push(qnode(nsum, nrow, ncol));
            }
        }
    }
}

int main()
{
    static int d[80][80];
    FILE *fi = fopen(FILENAME, "r");
    for(int r=0; r<80; r++) for(int c=0; c<80; c++)
        fscanf(fi, "%d%*c", &d[r][c]);
    fclose(fi);

    printf("ans = %d\n", solve1(d));
}