발전소

문제 분석 및 풀이

설계 분석

• 비트마스킹으로 같은 경로를 걸러내는 것이 중요한 문제
• 아래 과정을 P개 이상의 발전소가 켜질때 까지 반복
  • 켜진 발전기중 하나 선택 (i)
  • 꺼진 발전기중 하나 선택 (j)
  • j 켜기
  • i를 이용해서 j를 키는 비용을 추가
• 내 풀이는 P개 이상 켜졌을 때 전역변수에 최솟 값을 갱신하는 방법
• 더욱 최적화된 풀이는 각 상태의 최솟값을 배열에 저장해서 재사용

풀이

나의 풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;

const int INF = 987654321;
int N, P;

int graph[16][16];
int minimum = INF;
unordered_map<int, int> umap;

void dfs(int mask, int val)
{
    if (umap.find(mask) != umap.end())
    {
        int exsistingValue = umap[mask];
        if (exsistingValue <= val) return;
    }

    umap[mask] = val;

    int cnt = 0;
    for (int i = 0; i < N; ++i) {
        if ((mask >> i) & 1) { // i번째 비트가 1인지 확인
            cnt++;
        }
    }

    if (cnt >= P)
    {
        minimum = min(minimum, val);
        return;
    }

    for (int i=0; i<N; i++)
    {
        if (!(mask & (1 << i))) continue;
        for (int j=0; j<N; j++)
        {
            if (mask & (1 << j)) continue;
            dfs(mask | ( 1 << j ), val + graph[i][j]);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N;
    for (int i=0; i<N; i++)
    {
        for (int j=0; j<N; j++)
        {
            int weight;
            cin >> weight;
            graph[i][j] = weight;
        }
    }

    string onOffstat;
    cin >> onOffstat;
    int mask = 0;
    for (int i=0; i<onOffstat.size(); i++)
    {
        if (onOffstat[i] == 'Y')
        {
            mask |= 1 << i;
        }
    }

    cin >> P;

    dfs(mask, 0);
    minimum = minimum == INF ? -1 : minimum;
    cout << minimum;

    return 0;
}

개선 버전

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <cstring>
using namespace std;

const int INF = 987654321;
int N, P;

int graph[16][16];
int minimum = INF;
int cost[1 << 16];

int dfs(int mask)
{
    // 이미 값이 존재하면 그것을 리턴
    if (cost[mask] != -1)
    {
        return cost[mask];
    }

    // 켜진 발전소 개수
    int cnt = 0;
    for (int i = 0; i < N; ++i) 
    {
        if ((mask >> i) & 1) 
            cnt++;
    }

    // P개 이상이면 종료
    if (cnt >= P)
    {
        return 0;
    }

    cost[mask] = INF;
    // 현재 켜져있는 발전소에서 꺼진 발전소로 
    for (int i=0; i<N; i++)
    {
        // 켜저있는 발전소가 i
        if (!(mask & (1 << i))) continue;
        for (int j=0; j<N; j++)
        {
            // 꺼진 발전소가 j
            if (mask & (1 << j)) continue;
            // 현재 상태의 최솟값과, j발전 소를 킨 이후의 dfs값 + i에서 j를 키는 값
            cost[mask] = min(cost[mask], dfs(mask | ( 1 << j )) + graph[i][j]);
        }
    }

    return cost[mask];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
    // dp용 배열 -1로 초기화
    memset(cost, -1, sizeof(cost));
    
    // 입력
    cin >> N;
    for (int i=0; i<N; i++)
    {
        for (int j=0; j<N; j++)
        {
            int weight;
            cin >> weight;
            graph[i][j] = weight;
        }
    }

    string onOffstat;
    cin >> onOffstat;
    
    // 발전서 정보 초기회
    int mask = 0;
    for (int i=0; i<onOffstat.size(); i++)
    {
        // 켜진 경우는 비트마스킹
        if (onOffstat[i] == 'Y')
        {
            mask |= 1 << i;
        }
    }

    // 최소 P개 이상 켜져 있어야함
    cin >> P;

    minimum = dfs(mask);

    if (minimum == INF)
    {
        minimum = -1;
    }

    cout << minimum;

    return 0;
}