문제

이 문제는 디피도 알고 비트마스크도 알아야 풀 수 있는 훌륭한 문제다.

문제 링크

문제 접근

  • 이 문제를 어떻게 풀지 하다가 결국에는 방법을 봤다.
  • 비트마스크를 써야한다고 종만북의 비트마스크를 조금 공부해봤다.
  • 이 문제에 비트마스크를 어떻게 쓸까?

비트마스크를 활용한 집합의 표현

  • 비트마스크의 가장 주요한 사용 사례는 집합을 표현하는 것이다.
  • 여섯개의 원소를 가지는 집합 {1, 4, 5, 6, 7}을 표현하기 위해서는 이진수 $1011100010_2$을 이용하면 된다.
  • 단, 집합의 원소 개수가 많지 않다면 비트마스크를 이용해서 집합을 표현할 수 있다.

비트마스크와 디피

  • 부분집합의 형태와 최종 도착 도시의 비용을 담고 있는 dp 어레이를 하나 만든다.
int dp[1 << 16][16];
  • 0을 시작점으로 한다면 중간 과정 중에 0으로 돌아오면 안된다. 집합의 표현에서 0은 빼주도록 하자.
  • 이를 위해 집합의 원소가 1개인 경우의 값을 0에서의 각 원소까지의 비용으로 먼저 업데이트 해준다.(이 때 0에서 가는 길이 없는 경우는 제외한다.)
for(int i = 1; i < n; i++){
    if(w[0][i] == 0)continue;
    dp[1 << (i - 1)][i] = w[0][i];
}
  • 이제 1($001_2$)부터 시작해서 2^n -1($111_2$)까지 순회하면서 거리값을 업데이트 해나간다.
  • 업데이트의 방법은 부분집합 값에다가 원소가 1개짜리 부분집합(single)과의 합집합(sum)을 본다.
  • 이 때 합집합이 현재 집합과 같지 않다면 합집합의 값을 바꿔준다.
int single = 1 << (j - 1), sum = i | single;
if(sum == i) continue;
  • 합집합의 값은 현집합에서 최종 도시에서 출발해서 1개짜리 부분집합의 도시까지의 거리를 더해주면서 업데이트한다.
for(int k = 1; k < n; k++){
    if(dp[i][k] == INF || w[k][j] == 0)continue;
    if(dp[sum][j] > dp[i][k] + w[k][j])dp[sum][j] = dp[i][k] + w[k][j];
}
  • 그리고 최종적으로 dp[$111_2$][최종도시]에서 최종 도시부터 0번까지의 비용을 더해주고 최소값을 출력한다.
int ans = INF;
for(int i = 1; i < n; i++){
    if(dp[l - 1][i] == INF || w[i][0] == 0)continue;
    if(ans > dp[l - 1][i] + w[i][0])ans = dp[l - 1][i] + w[i][0];
}

최종 코드

#include <cstdio>
#define INF 987654321
int n, l, w[17][17], dp[1 << 16][16];

int main(){
    scanf("%d", &n);
    l = 1 << (n - 1);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++)scanf("%d", &w[i][j]);
    }
    for(int i = 1; i < l; i++){
        for(int j = 1; j < n; j++)dp[i][j] = INF;
    }
    for(int i = 1; i < n; i++){
        if(w[0][i] == 0)continue;
        dp[1 << (i - 1)][i] = w[0][i];
    }
    
    for(int i = 1; i < l; i++){
        for(int j = 1; j < n; j++){
            int single = 1 << (j - 1), sum = i | single;
            if(sum == i) continue;
            for(int k = 1; k < n; k++){
                if(dp[i][k] == INF || w[k][j] == 0)continue;
                if(dp[sum][j] > dp[i][k] + w[k][j])dp[sum][j] = dp[i][k] + w[k][j];
            }
        }
    }
    int ans = INF;
    for(int i = 1; i < n; i++){
        if(dp[l - 1][i] == INF || w[i][0] == 0)continue;
        if(ans > dp[l - 1][i] + w[i][0])ans = dp[l - 1][i] + w[i][0];
    }
    printf("%d", ans);
    
}

느낀점

  • 디피 뿐만 아니라 비트마스크를 공부하고 이렇게 문제도 풀 수 있어서 기뻤다.
  • 다음에도 이런 문제를 만나면 자신감 있게 도전해봐야겠다.