이번 문제는 백트레킹과 BFS를 통해 해결하였다. 우선 백트레킹을 통해 흰돌을 놓을 수 있는 모든 경우를 만들고, 이를 이용하여 돌들의 상황을 나타내는 리스트의 임시 리스트를 만들어 모든 경우를 각각 반영하여 BFS를 통해 탐색하도록 하였다. 탐색을 할 때에는 빈칸을 만날 경우 flag를 False로 변경해주어 해당 그룹의 돌들을 죽일 수 없음을 나타내야 한다. flag가 True로 유지된 상태로 탐색이 끝난다면 해당 그룹의 돌들의 수를 결과변수에 더해주었다.

Code

import copy
from collections import deque
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
possible = []
black = []
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
for i in range(n):
    for j in range(m):
        if grid[i][j] == 0:
            possible.append((i, j))
        if grid[i][j] == 2:
            black.append((i, j))
combs = []
def make_combs(cur, comb):
    if cur == len(possible):
        if len(comb) == 2:
            combs.append(comb)
        return
    if len(comb) > 2:
        return
    make_combs(cur+1, comb+[possible[cur]])
    make_combs(cur+1, comb)
def kill_black(grid, y, x):
    global answer
    q = deque()
    q.append((y, x))
    visited[y][x] = True
    path = [(y, x)]
    flag = True
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < m and not visited[ny][nx]:
                if grid[ny][nx] == 0:
                    flag = False
                elif grid[ny][nx] == 2:
                    visited[ny][nx] = True
                    path.append((ny, nx))
                    q.append((ny, nx))
    if flag:
        answer += len(path)
ans = 0
make_combs(0, [])
for comb in combs:
    answer = 0
    tmp_grid = copy.deepcopy(grid)
    for i in range(2):
        tmp_grid[comb[i][0]][comb[i][1]] = 1
    visited = [[False for _ in range(m)] for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 2 and not visited[i][j]:
                kill_black(tmp_grid, i, j)
    ans = max(ans, answer)
print(ans)