[Python] 백준 14391. 종이 조각

문제

처음엔 4x4 크기가 정해져있기 때문에 그냥 브루트포스로 풀면 풀릴 것이라 생각했지만.. 구현 자체가 막막했다.
칸마다 가로/세로/확장안함 3가지 경우를 나누고 접근했지만 틀렸다.

더 고민해본 후 풀이방법을 찾아봤는데 비트마스크를 써서 풀더라.
칸마다 가로/세로로 나눠 2가지 경우를 두고 NxM 칸이 모두 2가지 경우를 가지니 2^(NxM)-1의 경우를 갖는다. 이 2^(NxM)-1의 경우를 모두 순회하며 가로/세로일때로 경우를 또 나눠 가로칸, 세로칸의 합을 구한다.

2^(NxM)-1개의 경우를 순회하며 각 칸이 가로/세로인지 판단할 때 shift 연산과 & 연산을 활용한다.

코드

N, M = map(int, input().split())
arr = [list(map(int, input())) for _ in range(N)]

def bf():
  result = 0
  for i in range(1 << N * M):
      total = 0
      for row in range(N):
          srow = 0
          for col in range(M):
              idx = row * M + col
              if i & (1 << idx) != 0: srow = srow * 10 + arr[row][col]
              else:
                  total += srow
                  srow = 0
          total += srow

      for col in range(M):
          scol = 0
          for row in range(N):
              idx = row * M + col
              if i & (1 << idx) == 0: scol = scol * 10 + arr[row][col]
              else:
                  total += scol
                  scol = 0
          total += scol
      result = max(result, total)
  return result

print(bf())

참고

https://vixxcode.tistory.com/23