1102번: 발전소 - Baekjoon Online Judge

외판원 문제(TSP: Traveling Salesperson Problem)로 대표되는 NP-난해에 해당하는 문제이다. 외판원 문제는 여러 도시가 주어졌을때 외판원이 도시별로 이동하는데 드는 비용이 각각 다른 경우 모든 도시를 다 돌고오는데 드는 비용을 어떻게 최소로 만들 것인지를 물어보는 문제이다.

외판원 문제 - 위키백과, 우리 모두의 백과사전

https://ko.wikipedia.org/wiki/%EC%99%B8%ED%8C%90%EC%9B%90_%EB%AC%B8%EC%A0%9C

발전소 문제도 이와 유사하다. 여러 발전소가 주어지고 발전소가 켜져있는 경우 그 발전소를 이용하여 다른 발전소를 켤 수 있고 그때의 비용은 각각 다르게 주어진다. 이때 최소한 켜져야하는 발전소의 숫자가 주어졌을 때 그 발전소 개수만큼 켜는데 드는 최소비용이 얼마인지를 구하는 문제이다.

기본적으로 이 문제는 동적계획법 문제이다. 처음 주어지는 발전소 조건을 초기값으로 하여 발전소를 하나씩 더 킨다고 했을 때 최소비용을 갱신해가는게 이 문제를 푸는 점화식이 된다. 문제 자체를 푸는 방식은 이해가 가지만 16개의 발전소중 어떤게 켜지고 꺼졌는지를 체크해주는 것이 문제가 된다. 꺼지고 켜지고에 따라서 나올수 있는 가짓수는 2^16이나 되는데 이 모든 케이스를 구분하여 저장하기가 쉽지 않기 때문이다. 이때 사용하는 것이 비트마스크이다. 문제에서 발전소는 켜지고 꺼지는 두 가지 경우밖에 없고 그렇다면 이는 0과 1로 구분해주면 된다. 즉 발전소의 상태를 2진법으로 표시하여 16자리의 2진수를 통해 표시해주는 것이다. 1번 발전소는 2^0의 자리에 작동여부를 표시해주고 2번 발전소는 2^1의 자리에 3번 발전소는 2^2자리에 표시를 해주게 되면 총 2^15 범위내에서 16개 발전소의 작동여부를 표시해줄수 있게 되고 이는 10진수 65536 범위 내에서 모두 표시가 가능해진다.

15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
1	0	0	0	0	1	0	0	0	0	0	0	1	1	0	1

위와 같은 경우라면 자리수에 1을 더하여 계산한다고 했을 때, 1, 3, 4, 11, 16 발전소가 켜져있다는 것을 알 수 있고 2진수로 표시한다고 했을 때, 1000010000001101로 표시된다는 것을 알 수 있다. 

발전소 문제에서는 이 비트마스크를 이용하여 나올 수 있는 모든 경우의 수만큼 for문을 돌다가 작동중인 발전소를 발견하면, 그 발전소를 이용하여 작동하지 않고 있는 다른 발전소를 작동시킬 때의 비용을 최소비용으로 업데이트 해주는 방식으로 메모이제이션 해주면서 답을 구해주면 된다.

구현된 소스는 아래와 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    private static int[][] dp;
    private static final int SIZE = 1 << 16;
    private static final int MAX = (int) 1e9 + 1;
    private static int P;
    private static int N;
    private static int[][] E;
    private static String onOff;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        N = Integer.parseInt(br.readLine().trim());
 
        E = new int[N + 1][N + 1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine().trim());
            for (int j = 1; j <= N; j++) {
                E[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        dp = new int[SIZE][2];
        for (int i = 0; i < SIZE; i++) {
            dp[i][0] = MAX;
        }
        onOff = br.readLine().trim();
        int index = 0;
        int cnt = 0;
        for (int i = 1; i <= N; i++) {
            if (onOff.charAt(N - i) == 'Y') {
                index <<= 1;
                index += 1;
                cnt++;
            } else
                index <<= 1;
        }
        P = Integer.parseInt(br.readLine().trim());
        if (P == 0 || cnt >= P) {
            System.out.println(0);
            return;
        }
        if (cnt == 0) {
            System.out.println(-1);
            return;
        }
        dp[index][0] = 0;
        dp[index][1] = cnt;
        for (int i = 0; i < (1 << N); i++) {
            if (dp[i][0] == MAX)
                continue;
            for (int j = 1; j <= N; j++) {
                if ((i & (1 << (j - 1))) != 0) {
                    for (int k = 1; k <= N; k++) {
                        if ((i & (1 << (k - 1))) == 0) {
                            if (dp[i][0] + E[j][k] < dp[i + (1 << (k - 1))][0]) {
                                dp[i + (1 << (k - 1))][0] = dp[i][0] + E[j][k];
                                dp[i + (1 << (k - 1))][1] = dp[i][1] + 1;
                            }
                        }
                    }
                }
            }
        }
        int ans = MAX;
        for (int i = 0; i < (1 << N); i++) {
            if (dp[i][1] >= P) {
                if (dp[i][0] < ans)
                    ans = dp[i][0];
            }
        }
        System.out.println(ans);
    }
}