[백준 1014번] 컨닝 (Python3)

import sys
input = sys.stdin.readline

def DFS(n,bit,cnt):
  if DP[n][bit]:
    return
  if n == N-1:
    DP[n][bit] = cnt
    return
  for bit1,cnt1 in bitlist[n+1]:
    if bit&(bit1<<1) or (bit<<1)&bit1:
      continue
    DFS(n+1,bit1,cnt1)
    if DP[n][bit] < DP[n+1][bit1]+cnt:
      DP[n][bit] = DP[n+1][bit1]+cnt
    

T = int(input())
for _ in range(T):
  N,M = map(int,input().split())
  room = []
  for i in range(N):
    line = [*map(lambda x:1 if x=="x" else 0,[*input().strip()])]
    room.append(int(("".join(map(str,line))),2))

  bitlist = [[] for i in range(N)]
  for n in range(N):
    for bit in range(1<<M):
      if bit&room[n] or bit&(bit<<1):
        continue
      cnt = bin(bit).count("1")
      bitlist[n].append((bit,cnt))

  DP = [[0]*(1<<M) for i in range(N)]
  for bit,cnt in bitlist[0]:
    DFS(0,bit,cnt)

  print(max(DP[0]))

 

비트마스킹을 이용한 DP+DFS로 해결하는 문제이다.

외판원 순회 문제와 거의 비슷한 알고리즘으로 풀면 풀 수 있는 문제이다. 외판원 순회를 18번(...)이나 틀리면서 시행착오를 반복한 보람이 있는건지 꽤 쉽게 해결할 수 있었다.

 

알고리즘을 요약하면,

1. 일단 각 줄의 앉을 수 없는 자리와 앉을 수 있는 자리를 각각 1,0으로 취급하여 비트로 나타낸다.

2. 각 줄에서 앉을 수 없는 자리와 겹치지 않는 모든 bit 값을 구하고, 이때 1의 개수 (앉은 사람의 수)를 구하여 bitlist에 저장한다.

3. 비트마스킹을 이용한 DP+DFS로 역추적하여 최댓값을 구한다. 이때 현재 자리에서 1 shift한 값과 겹치지 않는 경우에 대해서 값을 갱신해준다. (앉을 수 없는 자리의 특성을 생각하자)

4. 최댓값을 구한다.

 

 

이 문제를 풀고 싶은 사람이 있다면 외판원 순회 문제를 먼저 풀고 이 문제를 푸는 것을 추천한다. 외판원 순회를 18번이나 틀린 보람을 느낄 수 있는 문제였다.

 

오늘의 교훈) 많이 틀리는것도 경험이라고 생각하자