[DP][Bitmask]BOJ 1102_발전소

문제 링크 : www.acmicpc.net/problem/1102

1102번: 발전소

 

DP와 Bitmask를 활용해 해결할 수 있는 문제이다. Bitmask에 대해서는 다음 링크에 설명해 두었다.

 

4legs-study.tistory.com/5

Bitmask 에 대해

 

각각의 발전소를 on/off 상태로 나타낼 수 있으므로,

모든 발전소에 대해 특정 발전소가 켜져 있는 전체 상태(State)를 Bitmask로 나타낼 수 있다.

 

특정 State에서 켜져 있는 i번째 발전소와 그 발전소를 통하여

켤 수 있는 모든 j번째 발전소에 대해, 그 발전소를 켰을 때의 newState는 Bitmask를 통해

newState = State | 1 << (i - 1)

과 같이 나타낼 수 있을 것이다. (첫 번째 발전소를 0번이 아닌 1번이라 가정했을 때)

 

이러한 연산을 통해 newState로 이동할 수 있는 최소비용이 곧 dp[newState]가 된다.

 

 

예를 들어 현재 발전소의 State가 Bitmask로 10001일 때, 10111 State로 가는 방법은 두 가지일 것이다.

1. 10001 --(2번째 발전소 on)--> 10011 --(3번째 발전소 on)--> 10111

2. 10001 --(3번째 발전소 on)--> 10101 --(2번째 발전소 on)--> 10111

 

1의 경우, 10111 상태로 가는 비용은 

 min(1->2 비용, 4->2 비용) + min(1->3 비용, 2->3 비용, 4->3 비용) 

 

2의 경우는

 min(1->3 비용, 4->3 비용) + min(1->2 비용, 3->2 비용, 4->2 비용)

 

최종적으로 10001 상태에서 10111 상태로 가는 최소비용은 1, 2 경우의 최소 결과값이 된다.

 

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
 
#define INF 100000000
 
using namespace std;
 
int genval[17][17];
int dp[1<<17];
int turnon, total, goal, oncnt, n;
 
int recursive(int turnon) {
    //ret은 dp[turnon]의 Reference. 즉, ret = dp[turnon]
    int& ret = dp[turnon];
    //dp[turnon]이 새 값으로 채워진 상태라면 그 값을 반환
    if (ret != -1) return ret;
    if (oncnt >= goal) return ret = 0;
    ret = INF; oncnt++;
 
    for (int i = 0; i < n; i++) {
        if (turnon & (1 << i)) {
            //켜져 있는 i 번째 발전소에 대해
            for (int j = 0; j < n; j++) {
                if (!(turnon & (1 << j))) {
                    //꺼져있는 j 번째 발전소를 켠다
                    ret = min(ret, recursive(turnon | (1 << j)) + genval[i][j]);
                    //비교 : 현재 저장된 dp[newState]와 i에서 j번째 발전소를 켠 후 최종 비용
                }
            }
        }
    }
    oncnt--;
    return ret;
}
 
int main() {
    fill(dp, dp + (1 << 17), -1);
    string onlist;
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> genval[i][j];
        }
    }
    cin >> onlist;
    for (int i = 0; i < onlist.size(); i++) {
        if (onlist[i] == 'Y') {
            //최초 켜진 상태를 비트마스크로 저장
            turnon |= (1 << i);
            oncnt++;
        }
    }
    cin >> goal;
    int answer = recursive(turnon);
 
    if (answer == INF) cout << -1 << endl;
    else cout << answer << endl;
 
    return 0;
}
 

조금 특이하게도 Bottom-Up 방식이면서 재귀호출을 이용했지만 일반적인 Bottom-Up과 동일하게 작동한다.