[BOJ] 1102. 발전소 (💎, 비트마스킹)

🔗

풀이

발전소는 최대 16개이고 모든 발전소는 켜져 있거나/꺼져 있는 , 두 가지 상태를 가지게 된다. 켜진 상태를 1이라고 하고 꺼져 있는 상태를 0이라고 하자.

켜진 발전소로만 꺼져 있는 발전소를 작동시킬 수 있으므로 우선 작동시킬 꺼진 발전소를 찾은 후 해당 발전소를 어떤 켜져 있는 발전소로 킬 건지를 찾게 된다.

먼저 꺼진 발전소를 찾은 후, 해당 발전소를 키기 위해 최소한의 비용이 필요한 켜진 발전소를 찾아 꺼진 발전소를 키면 된다. 이때 꺼진 발전소를 켜서 완성되는 발전소의 작동 상태를 보고 해당 작동 상태가 되기 위해 드는 비용이 기존에 들던 비용보다 적은 경우에만 해당 방식으로 꺼진 발전소를 작동시킨다.

이때 dfs + dp를 사용하게 되는데 동작 과정은 다음과 같다.

비트 탐색이기 때문에 탐색은 오른쪽에서 왼쪽으로 이루어지게 된다. 먼저 101001(41)이라는 숫자가 있을 때 꺼진 발전소 중 빨간색으로 표시 된 두 개의 발전소를 킨다고 가정하자. 오른쪽에 좀 더 가까운 발전소를 먼저 탐색하게 되기 때문에 해당 번호 순서대로 탐색하게 된다. 오른쪽에서 3번째에 있는 발전소를 킨 다음, 왼쪽에서 두 번째 있는 발전소를 키는 과정까지가 1, 2번 과정이다. 마지막 남은 하나의 발전소를 키면 3번이 되고 조건을 만족하게 된다(여기서는 P=6이라고 가정). 비트 111111은 조건 (cnt >= P)을 만족하기 때문에 return 0을 반환하게 되고 dp[111111] 아래와 같은 값을 갖게 된다.

dp[111111] = Math.min(dp[111111], 0 + power[j][i])

dp의 모든 초기값은 INF이기 때문에 아마도 dp[111111] = power[j][i]가 될 것이다.

재귀 방식이기 때문에 차례대로 함수가 반환되면서 위와 같은 과정을 거치게 되고 dp[111101]과 dp[101101]에도 값이 채워지게 된다.

이제 다시 처음 상태로 되돌아와서 이번에는 왼쪽 두번째 발전소를 먼저 키는 방식을 택하게 된다. 그런데 왼쪽 두번째를 킨 후, 오른쪽 세번째 발전소를 키게 되면 아까 이미 탐색했던 dp[111101]을 다시 지나게 된다. 이미 dp[111101]은 초기화 값인 INF가 아닌 새로운 값으로 갱신되어 있을 것이다. 오른쪽에서 세번째 발전소를 먼저 키는 과정에서 이미 방문한 곳이기 때문에 굳이 두 번 방문할 필요는 없는 것이다. 현재까지 오는 과정이 어떻든가와 상관없이 앞으로 111101에서 방문하게 될 경로는 이전에 미리 지나온 경로이기 때문이다. 이 과정에서 dp를 사용하게 되는 것이다.

dp[cur]에 저장된 값이 초기화된 값이 아니면 이미 방문한 곳이므로 해당 값을 재사용하고 return

이때 dp배열은 굳이 2차원일 필요가 없는데 각 비트값이 가질 수 있는 켜야 하는 발전소의 개수는 이미 다 정해져있기 때문이다. 101010을 초기값이라고 했을때 111110은 무조건 2개를 켜야 하고, 111010은 무조건 한개를 켜야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int P;
    static int[][] power;
    static int[] dp;
    static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        power = new int[N][N];
        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                power[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        String powerState = br.readLine();
        P = Integer.parseInt(br.readLine());

        int curVar = 0;
        int initCnt = 0;
        for (int i = 0; i < N; i++) {
            if (powerState.charAt(i) == 'Y') {
                curVar |= (1 << i);
                initCnt++;
            }
        }

        dp = new int[1<<N];
        Arrays.fill(dp, INF);
        if (initCnt >= P) dp[curVar] = 0;
        dfs(curVar, initCnt);
        System.out.println(dp[curVar] == INF ? -1 : dp[curVar]);
        // System.out.println(Arrays.toString(dp));
    }

    static int dfs(int cur, int cnt) {
        if (cnt >= P) return 0;
        if (dp[cur] != INF) return dp[cur];
        
        for (int i = 0; i < N; i++) {
            if ((cur & (1 << i)) != 0) continue; // 이미 켜진 발전소라면 지나감

            for (int j = 0; j < N; j++) {
                if ((cur & (1 << j)) == 0) continue; // 꺼진 발전소로는 다른 꺼진 발전소를 킬 수 없으므로 지나감
                
                dp[cur] = Math.min(dp[cur], dfs(cur | (1 << i), cnt + 1) + power[j][i]);
            }
        }
        return dp[cur];
    }
}