[백준 1102번] 발전소 (Python3)

import sys
input = sys.stdin.readline
INF = 10**6

def DFS(bit):
  if bin(bit).count("1") >= P:
    DP[bit] = 0
    return
  if DP[bit] != INF:
    return
  for next in range(N):
    if bit&(1<<next):
      continue
    if DP[bit|(1<<next)]==INF:
      DFS(bit|(1<<next))
    for now in range(N):
      if not bit&(1<<now):
        continue
      DP[bit] = min(DP[bit],DP[bit|(1<<next)]+graph[now][next])
      

N = int(input())
graph = []
for i in range(N):
  graph.append([*map(int,input().split())])

data = input().strip()
bit = 0
for i in range(N):
  if data[i] == "Y":
    bit |= 1<<i
P = int(input())

DP = [INF]*(1<<N)
if bit:
  DFS(bit)
  print(DP[bit])
else:
  if P == 0:
    print(0)
  else:
    print(-1)

전형적인 비트마스킹 DP 문제.

발전소가 켜져있는 것과 꺼져있는 것을 비트로 표현하고, DFS+DP로 풀이하면 된다.

 

알고리즘 자체는 외판원 순회 [백준 2098번] 외판원 순회 (Python3) (tistory.com) 보다 더 쉽다.

DP를 2차원으로 만들어야하는 외판원순회와 다르게 1차원으로도 충분하기 때문

 

다만 예외처리를 해야하는 부분이 까다로웠는데, 이 문제도 그놈의 0이 문제였다.

맨 처음 시작부터 bit가 0이면 -1을 출력해야하는것과, bit가 0이더라도 P가 0이면 0을 출력해야하는 것, 이 두 가지 때문에 애를 좀 먹었다.

 

이 점만 주의하면 풀이과정 자체는 어려울게 없다. 왜 이 문제가 플래티넘이고 외판원 순회가 골드인지 이해가 안가는...

 

 

오늘의 교훈) 0일때의 예외를 항상 조심, 또 조심