[C/C++] 프로젝트 오일러 #82 path sum : three ways(다익스트라)

이번 문제는 앞에 #81 문제와 동일하게 경로의 합을 구하는데 있어서 최소의 경로값을 잦는 것입니다.

앞의 문제가 two ways였던 것에 비해서 이번 것은 three ways입니다.

 

path sum : three ways

 

프로젝트 오일러 문제들 초창기가 제가 알고리즘 문제들 풀기 시작한 초기였던 점을 생각했을 때, 지금 보면 유치하기 짝이 없네요.

일단 힙구조를 사용하지도 않고 짰고, 삽입정렬을 이용해서 짰네요.  뭐 삽입정렬을 한다고 한다면, \(O(N^2)\) 알고리즘이었다는 것이죠.

 

이것 작성할 때만 해도 STL 사용도 안 했을 때이니까요.  우선순위 큐를 사용하면 해결되었을텐데요.

 

행렬이 크기 않았기 때문에 풀 수 있던 것이죠.

 

동적 계획법으로 풀 수도 있습니다.  하지만 사이클이 있기때문에 반복을 많이 해야 안정된 값이 나오게 됩니다.

그러니 다익스트라 알고리즘을 사용하는 것이 효율적이겠죠.

 

#81은 임의의 행렬 원소 입장에서 볼 때, 그 값을 결정할 수 있는 값이 같은 행에 있는 이전 값이나 같은 열에 있는 이전값이기 때문에 순차적으로 구할 수 있었죠.

 

제가 작성한 소스입니다.  지금 보면 좀 우습기도 합니다만, 참고용으로 봐주세요.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <time.h>

#define    FILENAME    "p082_matrix.txt"

static unsigned m[80][80];
static int queue[6400], sp = 0, ep = 0;

void push(int idx)
{
    int v = m[idx/80][idx%80];
    for( int i = sp ; i < ep ; i++ )
    {
        if( queue[i] == idx )
        {
            while( i > sp && m[queue[i-1]/80][queue[i-1]%80] > v )
            {
                queue[i] = queue[i-1];
                i--;
            }
            queue[i] = idx;
            return;
        }
    }
    int i = ep++;
    while( i > sp && m[queue[i-1]/80][queue[i-1]%80] > v )
    {
        queue[i] = queue[i-1];
        i--;
    }
    queue[i] = idx;
}

int pop()
{
    if( sp == ep ) return -1;
    return queue[sp++];
}

void solve1()
{
    static int matrix[80][80];

    FILE *fi = fopen(FILENAME, "r");

    for( int i = 0 ; i < 80 ; i++ )
    {
        char line[512];
        fgets(line, 512, fi);
        int j = 0;
        for( char *p = strtok(line, ",") ; p ; p = strtok(0, ",") )
        {
            matrix[i][j++] = atoi(p);
        }
    }

    fclose(fi);

    memset(m, -1, sizeof(m));
    for( int i = 0 ; i < 80 ; i++ )
    {
        m[i][0] = matrix[i][0];
        push(i*80);
    }

    int idx;
    while( (idx = pop()) != -1 )
    {
        int r = idx/80, c = idx%80;
        if( r > 0 && m[r-1][c] > m[r][c]+matrix[r-1][c] ) { m[r-1][c] = m[r][c]+matrix[r-1][c]; push(idx-80); }
        if( r < 79 && m[r+1][c] > m[r][c]+matrix[r+1][c] ) { m[r+1][c] = m[r][c]+matrix[r+1][c]; push(idx+80); }
        if( c < 79 && m[r][c+1] > m[r][c]+matrix[r][c+1] ) { m[r][c+1] = m[r][c]+matrix[r][c+1]; push(idx+1); }
    }

    unsigned min = m[0][79];
    for( int i = 1 ; i < 80 ; i++ )
    {
        if( min > m[i][79] ) min = m[i][79];
    }

    printf("Ans = %u\n", min);
}

int main()
{
    clock_t t;

    t = clock();

    solve1();

    printf("Elapsed time is %.3f seconds \n", (float)(clock()-t)/CLOCKS_PER_SEC);
}