BOJ - 16988 - A → B

import sys
from collections import deque

result = 0

def BFS(Baduk, N, M):
    global result
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]

    check = [[False for _ in range(M)] for _ in range(N)]

    ret = 0
    for i in range(N):
        for j in range(M):
            if Baduk[i][j] == 2 and check[i][j] is False:

                rock = deque()
                rock.append((i, j))
                cnt = 1
                flag = False
                check[i][j] = True

                while rock:
                    x, y = rock.popleft()
                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]

                        if 0 <= nx < N and 0 <= ny < M and check[nx][ny] is False:

                            if Baduk[nx][ny] == 0:
                                flag = True
                            elif Baduk[nx][ny] == 2:
                                cnt += 1
                                rock.append((nx, ny))
                                check[nx][ny] = True
                    if flag:
                        cnt = 0
                if not flag:
                    ret += cnt

    result = max(ret, result)

def setBaduk(Baduk, N, M, cnt):
    if cnt == 2:
        BFS(Baduk, N, M)
        return

    for i in range(N):
        for j in range(M):
            if Baduk[i][j] == 0:
                Baduk[i][j] = 1
                setBaduk(Baduk, N, M, cnt + 1)
                Baduk[i][j] = 0

def solution():
    N, M = map(int, sys.stdin.readline().split())
    Baduk = []

    for _ in range(N):
        Baduk.append(list(map(int, sys.stdin.readline().split())))

    setBaduk(Baduk, N, M, 0)
    print(result)
solution()

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