[BOJ 8890] Critical 3-Path

 2012 ACM-ICPC Daejeon regional 의 기출문제입니다. 백준 8890 에서 채점할 수 있습니다.

요약 )

 동적계획법으로 해결할 수 있는 문제로, DP 문제의 정의를 아래와 같이 하면 dp[t1][t2][t3]로 정답을 알 수 있습니다.

 dp[i][j][k] = s1 -> i, s2 -> j, s3 -> k 로 갈 때의 정답 (3개의 경로의 가중치 합의 최대값)

 주의해야 할 것은 경로 상의 정점이 중복되면 안된다는 점입니다. 간단한 DP 문제 정의로도 해결 가능함에도, 이 중복 제거 조건 때문에 문제가 까다롭게 느껴질 수 있습니다.

 이 풀이에서는 max(i,j,k) =  1 인 dp[i][j][k]들부터, max(i,j,k) = n 인 dp[i][j][k]들까지, max(i,j,k) 순서대로 DP 배열을 구함으로서 중복 문제를 해결합니다. max(i,j,k) 가 i, j, k 세 자리 중에서 한 곳에만 들어갈 수 있도록 하면 중복을 피할 수 있기 때문입니다.

입력 & 초기화 )

// code by RiKang, weeklyps.com
#include <bits/stdc++.h>
using namespace::std;
 
const int N = 105;
const long long INF = -((long long)1<<60);
 
int n,m;
int s1,s2,s3,t1,t2,t3;
long long edge[3][N][N];
long long dp[N][N][N];
 
void input(){
    scanf("%d %d",&n, &m);
    for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) for(int k=0; k<3; k++) edge[k][i][j] = INF;
    for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) for(int k=0; k<=n; k++) dp[i][j][k] = INF;
    scanf("%d %d %d %d %d %d",&s1,&s2,&s3,&t1,&t2,&t3);
    for(int i=1; i<=m; i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        edge[0][u][v] = edge[1][u][v] = edge[2][u][v] = w;
    }
    edge[0][0][s1]=edge[1][0][s2]=edge[2][0][s3]=0;
}

 기본적인 입력과 초기화입니다. 초기화는 -2^60으로 하였고,  구현의 편의성을 위해 edge를 여러 개 만들어 놓았습니다.

DP배열 구하기 )

// code by RiKang, weeklyps.com
void solve(){
    dp[0][0][0] = 0;
    for(int i=1; i<=n; i++){
        for(int j=0; j<i; j++) for(int k=0; k<i; k++) for(int l=0; l<i; l++){
            dp[i][k][l] = max(dp[i][k][l], dp[j][k][l]+edge[0][j][i]);
            dp[j][i][l] = max(dp[j][i][l], dp[j][k][l]+edge[1][k][i]);
            dp[j][k][i] = max(dp[j][k][i], dp[j][k][l]+edge[2][l][i]);
        }
    }
    printf("%lld\n",dp[t1][t2][t3]<0?0:dp[t1][t2][t3]);
}

 위의 코드와 같이, dp의 세 요소 중 최대값이 될 i 를 세 군데 중에서 한 곳에만 넣어주면 중복을 피할 수 있습니다. dp[i][k][l] 에서 k와 l이 i와 같은 값일 리는 당연히 없고, 또한 한 번 i=a가 지나고 나면 i++ 이후로는 다시 a가 돌아오지 않기 때문에, 나중에 다른 경로가 a를 거칠 일도 없습니다. 그러므로 그대로 간단한 점화식을 넣어주면 됩니다.

 dp[0][0][0]=0 이 아니라 dp[s1][s2][s3]=0 으로 시작하였을 때 문제가 될 수 있는 것은 dp[s1][s2][s3] -> dp[s2-1][s2][s3] 식으로 갈 수 있는 경우입니다. s2-1 < s2 이기 때문에, 이 풀이에서는 제대로 갱신되지 않습니다. 따라서 dp[0][0][0]=0 부터 시작하며, 대신 초기화에서 한 edge[0][0][s1] = edge[1][0][s2] = edge[2][0][s3]=0; 을 통해 자연스럽게 s1, s2, s3에서 시작할 수 있도록 하였습니다.

최종 코드 )

// code by RiKang, weeklyps.com
// 2012 ACM-ICPC Daejeon regional - C
// BOJ 8890 Critical 3-Path
 
#include <bits/stdc++.h>
using namespace::std;
 
const int N = 105;
const long long INF = -((long long)1<<60);
 
int n,m;
int s1,s2,s3,t1,t2,t3;
long long edge[3][N][N];
long long dp[N][N][N];
 
void input(){
    scanf("%d %d",&n, &m);
    for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) for(int k=0; k<3; k++) edge[k][i][j] = INF;
    for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) for(int k=0; k<=n; k++) dp[i][j][k] = INF;
    scanf("%d %d %d %d %d %d",&s1,&s2,&s3,&t1,&t2,&t3);
    for(int i=1; i<=m; i++){
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        edge[0][u][v] = edge[1][u][v] = edge[2][u][v] = w;
    }
    edge[0][0][s1]=edge[1][0][s2]=edge[2][0][s3]=0;
}
 
void solve(){
    dp[0][0][0] = 0;
    for(int i=1; i<=n; i++){
        for(int j=0; j<i; j++) for(int k=0; k<i; k++) for(int l=0; l<i; l++){
            dp[i][k][l] = max(dp[i][k][l], dp[j][k][l]+edge[0][j][i]);
            dp[j][i][l] = max(dp[j][i][l], dp[j][k][l]+edge[1][k][i]);
            dp[j][k][i] = max(dp[j][k][i], dp[j][k][l]+edge[2][l][i]);
        }
    }
    printf("%lld\n",dp[t1][t2][t3]<0?0:dp[t1][t2][t3]);
}
 
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        input();
        solve();
    }
    return 0;
}