백준 1102 발전소

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

1102번: 발전소

이 문제는 백준 2098 외판원 순회와 비슷하면서 다르다.

 

가장 큰 차이점은 외판원 순회처럼 i도시에서 j도시로 가는게 아니라, 

켜져있는 어떤 발전소든지 꺼진 발전소를 재생시킬 수 있는 것이다.

즉 외판원 순회에서 방문한 도시는 다시 못가지만, 이 문제에서는 방문한 도시에서 다시 다른 도시로 또 갈 수 있는 것이다. 굳이 억지를 들자면, 다시 돌아가는 비용은 0인 상태이다.

 

그러면 코드에서 나타나는 가장 큰 차이는 dp배열이 1차원이 된다는 것이다.

상태값에 따라 값을 저장하면 된다. 어차피 꺼진 발전소는 다른 켜진 발전소 어디에서 켜도 되므로, 나의 '현재 위치' 같은 정보가 필요하지 않다. 단지 지금까지 몇개의 발전소를 켰는지만 체크하면 된다. 일종의 재귀 depth가 되겠다.

 

<코드>

재귀, DP

 

<코드>

import sys
si = sys.stdin.readline

n, w, big = int(si()), [], 36*16+1
dp = [-1 for _ in range(1 << n)]
for _ in range(n):w.append([int(e) for e in si().split()])
plants, cnt, mask, curr = si()[:-1], int(si()), 0, 0

for i in range(n):
    if plants[i] == 'Y':
        mask |= 1 << i
        curr += 1


# 이미 모든 조건이 만족된 상태
if not cnt or curr >= cnt:
    print(0)
    sys.exit()


# 문제의 조건을 만족할 수 없는 경우
if cnt > n or not curr:
    print(-1)
    sys.exit()


def solve(mask, num):
    global n, cnt, big

    if num == cnt:
        return 0
    if dp[mask] != -1:
        return dp[mask]

    dp[mask] = big

    for i in range(n):
    	# 켜진 발전소를 찾는다
        if not ((1 << i) & mask):continue
        for j in range(n):
        	# 꺼진 발전소를 찾는다
            if (1 << j) & mask:continue
            dp[mask] = min(dp[mask], w[i][j] + solve((1 << j) | mask, num+1))

    return dp[mask]


print(solve(mask, curr))