[BOJ-4883]삼각그래프

https://www.acmicpc.net/problem/4883

위 그림에서 가장 위쪽 중앙 노드에서 가장 아래 중앙 노드까지 가는 최소 비용을 구하는 문제이다.

노드를 방문할 때마다 노드에 적힌 값을 더하게 된다.

[접근방법]

먼저,

각 노드에 도달할 때 도달할 수 있는 비용을 저장하기 위한 dp 테이블을 설정한다.

이용할 수 없는 노드는 INF으로 설정한다. 이용할 수 없는 노드는 0,0 에 위치한 노드이다.

0,0 의 노드는 시작 노드 이전 노드이므로 필요가 없다. 

무조건 시작노드는 0,1 의 노드가 된다. 0,2 노드는 시작노드가 0,1이므로 0,1 에 자신에 노드에 있는 값을 더해야만 한다. 

먼저 dp 테이블을 INF으로 초기화한다. 

0,1 dp테이블은 노드가 가진 값을 넣어주고,

0,2 에는 0,1 값을 더해준다.

이를 이용하여 현재 구할 노드의 위치를 dp[tr][tc] 라고 하자. 현재 위치에서 최소가 되는 값을 갱신시키기 위해서 

min(dp[tr][tc], dp[hr][hc]+node[tr][tc]) 으로 구할 수 있다. 

dp[hr][hc] : 

hr - here row

hc - here col

dp[tr][tc] :

tr - there row

tc - there col

그리고 값을 비교할 위치는 계산이 끝난 지난 dp 값들을 이용한다. 

그러면 총 4가지 경우로 값이 내려올 수 있다. 하지만 C 의 범위는 [0,2] 까지 이므로 따로 조건을 걸어 continue; 시켜준다.

현재 위치[hr][hc]에서 계산된 이전 위치[tr][tc]는 4가지 경우이다. 다만 구하는 경우에 따라 2, 3, 4가지 일 수 있다. (범위) 

1. [hr+1][hc-1]
2. [hr+1][hc]
3. [hr+1][hc+1]
4. [hr][hc+1]

이를 이용하여 갱신시키고, 마지막 위치의 중앙에 위치한 dp 값을 출력하면 문제를 해결할 수 있었다.

[C++11 source code DP]

#include<cstdio>
#include<memory.h>
 
const int M = 111111;
const int dr[] = { 0,1,1,1 };
const int dc[] = { 1,1,0,-1 };
const int INF = 1 << 25;
int imap[M][3];
int dp[M][3];
 
int mn2(int a, int b) { return (a > b) ? b : a; }
 
int main() {
    int tc = 1;
    int n;
    while (scanf("%d", &n) == 1) {
        if (n == 0) break;
        printf("%d. ", tc++);
        memset(imap, 0x00, sizeof(imap));
 
        for (int r = 0; r < M; r++) {
            for (int c = 0; c < 3; c++) {
                dp[r][c] = INF;
            }
        }
 
        for (int r = 1; r <= n; r++) {
            for (int c = 0; c < 3; c++) {
                scanf("%d", &imap[r][c]);
                if (r == 1) {
                    dp[r][c] = imap[r][c];
                }
            }
        }
        dp[1][2] += dp[1][1];
        dp[1][0] = INF;
 
        for (int hr = 1; hr <= n; hr++) {
            for (int hc = 0; hc < 3; hc++) {
                for (int i = 0; i < 4; i++) {
                    int tr = hr + dr[i];
                    int tc = hc + dc[i];
                    if (tc < 0 || 3 <= tc) continue;
                    dp[tr][tc] = mn2(dp[tr][tc], dp[hr][hc] + imap[tr][tc]);
                }
            }
        }
        
        printf("%d\n", dp[n][1]);
 
    }
    
    return 0;
}