> 문제 <

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

> 코드 설명 <

• 백트래킹

  벽 1개 build -> wall(1) -> 벽 1개 고정, 벽 1개 build -> wall(2)
  -> 벽 2개 고정, 벽 1개 build (총 벽 3개 완공) -> wall(3) -> bfs() -> ... -> return
  -> cnt = 2인 상태, 최근 벽(3번째 벽) 허물기 -> 3번 벽 새로 build (j + 1) -> wall(3) -> ...

  ---

  이런 식으로 고정(벽 1,벽 2), 벽3 완전 탐색 .. -> 벽1(고정), 벽2(1칸 이동), 벽3(완전 탐색)
  [for 벽1 for 벽2 for 벽3] >>> 이런 느낌
  모든 경우의 수를 다 탐색하는 문제.

> 코드 <

from collections import deque
import sys
import copy

n, m = map(int, sys.stdin.readline().split())
space = []
for _ in range(n):
    space.append(list(map(int, sys.stdin.readline().split())))

d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
max_safe = 0


def bfs():  # 전염
    global max_safe
    ans = copy.deepcopy(space)
    queue = deque()
    for i in range(n):
        for j in range(m):
            if ans[i][j] == 2:
                queue.append((i, j))
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + d[i][0], y + d[i][1]
            if 0 <= nx < n and 0 <= ny < m and ans[nx][ny] == 0:
                ans[nx][ny] = 2
                queue.append((nx, ny))

    result = checkSafe(ans)
    # for i in range(n):
    #     result += ans[i].count(0)             # count는 시간 오래 걸림
    max_safe = max(result, max_safe)


def checkSafe(ans):
    cnt = 0
    for i in range(n):
        for j in range(m):
            if ans[i][j] == 0:
                cnt += 1
    return cnt


def wall(cnt): 					 # backTracking (백트래킹) 벽 세우기
    if cnt == 3:
        bfs()
        return

    for i in range(n):
        for j in range(m):
            if space[i][j] == 0:
                space[i][j] = 1   # 벽 세움
                wall(cnt + 1)
                space[i][j] = 0   # 다시 허문다

wall(0)
print(max_safe)

> 배운 점 <

.count()는 시간이 매우 오래 걸린다.
2차원 배열에서 0인 원소만 찾고 싶다면, .count()보다 차라리 이중 for문과 == 을 이용해
직접 카운팅을 해주는 것이 빠르다

메모리도 별 차이 없다.

• 조합

s = [[2, 0, 0, 0, 1, 1, 0], [0, 0, 1, 0, 1, 2, 0], [0, 1, 1, 0, 1, 0, 0], [0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 1], [0, 1, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0]]
blank = []
for i in range(len(s)):
    for j in range(len(s[0])):
        if s[i][j] == 0:
            blank.append([i, j])				 # 0인 좌표들
for combi in list(combinations(blank, 3)):		 # 0인 좌표들 중 3개 조합들
    print(combi)

이런 식으로 3개씩 묶어서 나올 수 있는 조합들을 뽑아낼 수 있다.
space에서 빈칸인 부분들을 3개씩 조합해(3개의 벽) 벽을 놓을 수 있는 모든 경우의 수를 combinations() 로 한번에 뽑아낼 수 있는 것이다.

using 조합 코드 참고 : https://developer-ellen.tistory.com/38