[ 백준 1102 ] 발전소 (C++)

백준의 발전소(1102) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 적어도 P개의 발전소가 고장나 있지 않도록, 발전소를 고쳐야 하는데 드는 비용의 최소값을 구해야 하는 문제이다.

   본인은 이 문제를 비트마스크와 메모이제이션을 이용해서 구현해 보았다.

   비트마스크를 사용한 이유는 '상태'를 저장하기 위함이다. 현재 몇 번 발전소가 고쳐져있는 상태인지, 어떤 발전소가

   고장나 있는 상태인지를 비트인 '1'과 '0'으로 쉽게 저장할 수 있기 때문이다.

   DFS + DP를 이용해서 구현하였는데, 이를 위해 선언한 변수부터 알아보자.

   본인은, Cost[] 라는 1차원 int형 배열을 사용했는데 Cost[a] = b 의 의미는 "a상태일 때 드는 최소비용은 b원입니다"를

   의미한다. 즉, 'a'가 들어가는 곳에는 우리가 위에서 말했던 상태를 저장하는 비트마스크들을 십진수로 변환한 값이

   들어간다.

   예를 들어서 Cost[00011] 이면, "1번과 2번 발전소가 켜져있고, 3, 4, 5번 발전소가 고장나 있을 때, 이 상태에서의 최소

   비용은 b원입니다"를 의미한다.

   DFS의 매개변수로는 [ 상태 ] 를 나타내는 int형 변수 하나만 가지고 진행해 주었다.

 

2) DFS함수 내에서 고칠 발전소를 탐색하는 과정은 다음과 같다.

   1. 현재 매개변수(무슨 발전소가 작동중인지 표시를 해놓은 비트)를 통해서 고장나지 않은, 즉, 작동중인 발전소를

     찾는다.

   2. 현재 매개변수를 통해서 고장난 발전소를 찾아서, 1번 과정에서 구한 발전소로, 해당 발전소를 찾는데 드는 비용을

     더하면서 DFS 재귀 호출을 진행한다.

   3. 1 ~ 2번의 과정을 반복한다.

[ 소스코드 ]

#include<iostream>
#include<string>
#include<cstring>
 
#define endl "\n"
#define MAX 16
#define INF 987654321
using namespace std;
 
int N, P, Answer = INF;
int MAP[MAX][MAX];
int Cost[1 << MAX];
string S;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
    cin >> S;
    cin >> P;
}
 
int Bit_Count(int B)
{
    int Cnt = 0;
    while(B != 0)
    {
        Cnt = Cnt + (B & 1);
        B = B >> 1;
    }
    return Cnt;
}
 
int DFS(int State)
{
    if (Bit_Count(State) >= P) return 0;
    if (Cost[State] != -1) return Cost[State];
 
    Cost[State] = INF;
    for (int i = 0; i < N; i++)    
    {
        if ((State & (1 << i))  == 0) continue;
        for (int j = 0; j < N; j++)
        {
            if ((State & (1 << j)) == 0)
            {
                int Next_State = State | (1 << j);
                Cost[State] = Min(Cost[State], MAP[i][j] + DFS(Next_State));
            }
        }
    }
    return Cost[State];
}
 
void Solution()
{
    int Bit_State = 0;
    for (int i = 0; i < S.length(); i++)
    {
        if (S[i] == 'Y') Bit_State = Bit_State | (1 << i);
    }
 
    memset(Cost, -1, sizeof(Cost));
    Answer = DFS(Bit_State);
 
    if (Answer == INF) cout << -1 << endl;
    else cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}