1102-발전소(Bitmask)

ㄴ

1102-발전소

외판원 순회 문제와 비슷한 유형인데, 차이점이라면 외판원 순회 문제는 반드시 모든 노드를 방문해야 했었다면 이 문제는 방문할 필요가 없는 노드(이미 가동되어 있는 발전소)가 존재하고, 또 p값이 n보다 작을 수 있다. 이 말은 곧 모든 노드를 방문할 필요가 없다는 뜻이다.

외판원 순회 문제의 dfs함수 구조와 dp배열이 다르다. 그 이유는 모두 '현재 위치가 어디인지 상관 없기'때문이다. 외판원 순회 문제의 경우에는 현재 자신이 어느 노드에 위치해있느냐에 따라서 갈 수 있는 지점이 달라지는 반면에, 이 문제는 가동되어 있는(visited에서 1인)노드라면 어디든지 도달 가능하기 때문이다. 따라서 굳이 현재 위치를 기록할 필요가 없고 그에 따라 dfs함수와 dp배열에도 현재위치를 기록하는 부분이 없다. 

그리고 또 다른 차이점은 dfs함수 내에 2중 for문이 존재한다. 출발점을 나타내는 from부분과 도착점을 나타내는 to부분이다. 이 부분을 떠올려내기가 힘들었다. 외판원 순회 문제에서는 현재 위치하고 있는 cur에서 도달 가능한 곳만 고려하는 반면에 이 문제는 그렇지 않기 때문이다. 두 문제의 유형은 비슷하지만 차이점에 따라서 세부 구현이 어떻게 달라지는지 알게되었다.

#include<stdio.h>
#define INF 1<<10
int dp[1 << 17], dist[20][20];
int n, ans,p;
int fMin(int a, int b) {
    return a > b ? b : a;
}
int dfs(int cnt, int visited) {
    if (cnt >= p) {
        return 0;
    }
 
    if (dp[visited] != -1)
        return dp[visited];
 
    dp[visited] = INF;
 
    for (int from = 1; from <= n; from++) {
        if (visited & (1 << from)) { //가동된 발전소에서만 이동 가능
            for (int to = 1; to <= n; to++) {
                if (from == to) continue; 
                if (visited & (1 << to)) continue; //이미 가동된 발전소는 방문할 필요 없음
                int next_visited = visited | (1 << to);
 
                dp[visited] = fMin(dp[visited], dfs(cnt + 1, next_visited)+dist[from][to]);
            }
        }
    }
 
    return dp[visited];
}
int main() {
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            scanf("%d ", &dist[i][j]);
        }
 
    for (int j = 0; j <= (1 << n+1); j++)
        dp[j] = -1;
 
    int init = 0, init_cnt = 0;
    for (int i = 1; i <= n + 1; i++) {
        char a; scanf("%c", &a);
        if (a == 'Y') {
            init |= (1 << i);
            init_cnt++;
        }
    }
    scanf("%d", &p);
 
    if (init_cnt == 0 && p!=0) //초기에 가동된 발전소가 0개라 하더라도, p=0이라면 답은 0이다. *사소한 예외처리
        ans = -1;
    else ans = dfs(init_cnt, init);
 
    printf("%d\n", ans);
 
    return 0;
}