[백준][Python] 16988 바둑2

문제 이름만 봐도 바킹독님이 만드신 문제.. 구현문제로 자주나오는 유형. 삼성 기출의 연구소 같은 느낌으로 막아놓을 벽을 몇개 정하고 BFS로 막힌 영역을 세는 느낌. 연구소 시리즈를 풀며 연습할 필요성을 느꼈다.

벽을 고르는 조합도 comb를 쓰지않고 함수를 구현하는 방법도 고려할 수 있다.

import sys
input = sys.stdin.readline
from collections import deque
from itertools import combinations

def BFS(x,y,visited):
    queue = deque()
    visited[x][y] = True
    queue.append([x,y])
    kill_ai_stone = 1
    flag = 0
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < N and 0 <= ny < M and not visited[nx][ny]:
                if baduk_board[nx][ny] == 0:
                    flag = 1
                elif baduk_board[nx][ny] == 2:
                    visited[nx][ny] = True
                    kill_ai_stone += 1
                    queue.append([nx,ny])
    return kill_ai_stone if not flag else -1


def play_game(put_stone):
    visited = [[False]*M for _ in range(N)]
    kill_count = 0
    for x,y in put_stone:
        baduk_board[x][y] = 1
    for i in range(N):
        for j in range(M):
            if baduk_board[i][j]==2 and not visited[i][j]:
                cnt = BFS(i,j,visited)
                if cnt != -1:
                    kill_count += cnt
    for x,y in put_stone:
        baduk_board[x][y] = 0
    return kill_count
    

N, M = map(int,input().split())
baduk_board = []
dx = [0,0,-1,1]
dy = [-1,1,0,0]

pos = []
for i in range(N):
    row = list(map(int,input().split()))
    baduk_board.append(row)
    for j in range(M):
        num = row[j]
        if not num:
            pos.append((i,j))

max_kill_cnt = 0
for my_turn in combinations(pos,2):
    max_kill_cnt = max(max_kill_cnt,play_game(my_turn))
print(max_kill_cnt)