[BOJ] 발전소

[문제]

https://www.acmicpc.net/problem/1102

1102번: 발전소

[풀이]

1102

맞았습니다!!

2500 KB

24 ms

C++14 / 수정

1797 B

53초 전

 

1) 외판원 순회 (tsp) 문제이다. 

 

2) 비트마스크를 사용해서 켜져있는 발전소와 아닌 발전소를 구분했다. 

 

3) 지금 살펴보고 있는 발전소가 켜져있는 발전소면 현재의 비용과 다음에 나올 발전소를 키는 비용 중 최소값을 구한다. 

 

4) 이미 방문한 발전소를 구분하기 위해 각 발전소를 구분하는 값에 큰 정수를 넣어줬다. 

 

5) 가지치기 

• 켜져있는 발전소가 0개 일 경우 
  • p(켜져있어야 할 발전소 최소 개수) 가 0인 경우 -> 비용 0
  • else -> -1
• 켜져있는 발전소가 p 보다 큰 경우 -> 비용 0
• 그 외, tsp 호출

---

#include <iostream>
#include <cmath>
 
#define INF 987654321
using namespace std;
 
int n, fee[16][16], p;
int dp[1<<16 + 1]; //1->2->3->4 등 순서대로 발전소를 켤 이유가 없기 때문에 level은 만들지 않는다. 
char yorn[16];
 
int tsp(int cnt, int state) {
    //외판원 순회 문제 
 
    if (cnt == p) {
        return 0;
    }
 
    int& ret = dp[state];
 
    if (ret != INF) return ret;
    //이미 방문한 발전소 
    
    for (int i = 0; i < n; i++) {
        if ((state & (1<<i)) > 0) {
            //켜져있는 발전소라면 
            for (int j = 0; j < n; j++) {
                //꺼져있는 발전소를 찾는다. 
                if (i == j) continue;
 
                if ((state & (1<<j)) == 0) {
                    //꺼져있는 발전소라면 
                    //이 발전소를 켜는 비용이랑 현재 값을 비교해서 최소값을 구한다. 
                    ret = min(ret, tsp(cnt+1, (state | (1<<j)))+ fee[i][j]);
                }
            }
        }
    }
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> fee[i][j];
        }
    }
    
    for (int i = 0; i < n; i++) {
        cin >> yorn[i];
    }
 
    cin >> p;
    //input 
 
    int state = 0, cnt= 0;
 
    for (int i = 0; i < n; i++) {
        //켜져있는 발전소와 아닌 발전소를 비트로 구별한다.
        if (yorn[i] == 'Y') {
            state |= (1<<i);
            cnt++;
        //켜져있는 발전소의 비트 켜기 
        }
    }
 
    for (int i = 0; i < (1<<n); i++) {    
        dp[i] = INF; //최소비용을 구하기 위해 최대값으로 만들어줌 
    }
 
    //켜져있는 발전소가 하나도 없는 경우 -> 시작 불가능 
    if (cnt == 0) {
        if (p == 0) cout << 0 << '\n';
        else cout << -1 <<'\n';
    }
    else if (cnt >= p) {
        //더 켤 필요 없음 
        cout << 0 << '\n';
    }
    else {
        //tsp (외판원순회 )  
        cout << tsp(cnt, state) << '\n';
    }
    return 0;
 
}