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

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

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

 

path sum : three ways

 

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

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

 

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

 

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

 

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

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

 

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

 

path sums

 

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

//------------------------------------------------
//    Project Euler #82 - Path Sum: Three Ways
//        - by Aubrey Choi
//        - created at 2015-10-13
//------------------------------------------------
#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);
}

 

이 프로그램은 Project Euler 문제 #82를 해결하기 위한 C 코드입니다. 문제는 80x80 매트릭스에서 왼쪽 열에서 오른쪽 열로 이동할 때 최소 경로 합을 찾는 것입니다. 경로는 위, 아래, 오른쪽으로 이동할 수 있습니다.

다음은 코드의 주요 기능을 모듈별로 설명합니다:

1. 주요 상수 및 전역 변수
• FILENAME: 파일 이름(p082_matrix.txt)이 정의되어 있으며, 이 파일에서 매트릭스를 읽습니다.
• m[80][80]: 경로 합을 저장하는 2차원 배열입니다. 각 셀에서 도달 가능한 최소 합이 기록됩니다.
• queue[6400]: 우선순위 큐 역할을 하는 배열입니다. 크기는 80 x 80으로 최대 가능한 셀 개수를 커버합니다.
• sp (start pointer), ep (end pointer): 큐의 시작과 끝 인덱스를 나타냅니다.

2. 함수 설명

(1) push(int idx)
• 우선순위 큐에 새 인덱스를 삽입하는 함수입니다.
• 매트릭스 셀의 값(가중치)에 따라 정렬하여 큐에 저장합니다.
• 주요 동작:
• 큐를 순회하며 삽입할 위치를 결정합니다.
• 새 값이 더 작으면 이전 값을 이동시키고 올바른 위치에 삽입합니다.
• 이미 큐에 있는 인덱스면, 값의 갱신 여부를 확인합니다.

(2) pop()
• 큐의 맨 앞에 있는(가장 작은 가중치) 인덱스를 제거하고 반환합니다.
• 큐가 비어있으면 -1을 반환합니다.

(3) solve1()
• 메인 알고리즘으로, 매트릭스를 읽고 문제를 해결합니다.
• 주요 단계:
1. 파일에서 매트릭스 읽기
• 파일(p082_matrix.txt)에서 매트릭스를 읽어 matrix[80][80]에 저장합니다.
• 데이터를 콤마(,)로 구분하여 각 숫자를 변환합니다.
2. 초기화
• m 배열의 모든 값을 -1로 설정 (최대값 초기화).
• 왼쪽 열의 값을 m 배열에 복사하고 큐에 삽입합니다.
3. 다익스트라 알고리즘 수행
• 큐에서 인덱스를 하나씩 꺼내면서 인접한 셀(위, 아래, 오른쪽)로 확장합니다.
• 인접 셀에서 더 작은 경로 합이 발견되면 갱신하고 큐에 삽입합니다.
4. 최소 경로 합 계산
• 오른쪽 열의 값을 순회하여 가장 작은 값을 찾습니다.
• 결과를 출력합니다.

4. main()
• 프로그램 실행의 시작점입니다.
• 주요 동작:
1. 타이머 시작: clock()을 사용하여 시작 시간을 기록합니다.
2. solve1() 호출: 문제 해결을 수행합니다.
3. 시간 측정 및 출력: 소요 시간을 출력합니다.

다익스트라 알고리즘 요소
• 우선순위 큐: queue[]를 이용해 다익스트라 알고리즘에서 가장 작은 값을 빠르게 가져옵니다.
• 경로 업데이트:

if (r > 0 && m[r-1][c] > m[r][c] + matrix[r-1][c]) { ... }

현재 셀에서 상하좌우로 확장하며 최소 경로 값을 업데이트합니다.

전체 흐름
1. 매트릭스를 읽고 초기화.
2. 다익스트라 알고리즘을 사용해 최소 경로를 계산.
3. 오른쪽 열에서 최소 경로 합을 찾아 출력.

이 프로그램은 효율적인 메모리 관리와 경로 계산을 통해 문제를 빠르게 해결하도록 설계되었습니다.