백준 16988 Baaaaaaaaaduk2 (Easy) (파이썬)

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

16988번: Baaaaaaaaaduk2 (Easy)

문제를 풀지 못하여 다른 블로그의 글을 참고하였으나...가독성이 떨어지고 불필요한 코드가 있어 고생했다.

나같은 사람들이 없기를 바라면서 글을 정리한다.

풀이

이 문제는 BFS와 조합탐색을 이용해서 해결하는 문제이다.

문제를 해결하는 방법은 다음과 같다.

1. 상대측 돌의 그룹을 찾고 만약 상대측 돌의 그룹에 인접해 있는 빈 칸이 2개 이하이면 해당 그룹과 인접해있는 빈 칸의 좌표와 해당 그룹에 속해 있는 돌의 개수를 저장해놓는다.
2. 돌 2개로 잡을 수 있는 상대측 그룹의 조합을 구하고 이 때 잡을 수 있는 돌의 최대값을 갱신해나간다.

이 문제에서 어려웠는 것은 조합을 구하는 것였는데 이는 재귀적으로 호출을 하며 문제를 해결한다.

• 인자로는 지금까지 잡았는 상대측 돌의 개수, 상대측 돌을 잡는데 필요한 빈 칸들의 좌표에 대한 집합, 조합하기 위한 시작 인덱스를 의미한다.
• 만약 두번째 인자인 상대측 돌을 잡는데 필요한 빈칸들의 좌표에 대한 집합의 길이가 2 초과이면 해당 조합은 한번에 잡을수 없기에 재귀함수를 빠져나온다.
• 현재까지 구한 잡을수 있는 최대값(정답, ans)와 새롭게 구한 잡을수 있는 상대측 돌의 개수를 비교해 최대값을 업데이트 해준다.
• 현재 주어진 빈 칸에 대한 집합을 재정의하고 하고 현재까지 구해놓은 조합에 start부터 마지막 인덱스사이에 있는 그룹을 순차적으로 조합하며 함수를 재귀적으로 호출해준다.

import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()

dir_xs = [0, 1, 0, -1]
dir_ys = [1, 0, -1, 0]
group=[]
ans = 0

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

def inRange(x, y):
    return 0<= x < N and 0 <= y < M

def bfs(startX, startY):
    board[startX][startY] = 3
    cnt = 0

    q = deque([(startX, startY)])
    empty_spot = set()
    while q:
        x, y = q.popleft()
        cnt += 1

        for dir_x, dir_y in zip(dir_xs, dir_ys):
            nx = x + dir_x
            ny = y + dir_y

            if inRange(nx, ny):
                if (nx, ny) not in empty_spot and board[nx][ny] == 0:
                    empty_spot.add((nx, ny))
                if board[nx][ny] == 2:
                    board[nx][ny] = 3
                    q.append((nx, ny))
    
    if len(empty_spot) <= 2:
        group.append((empty_spot, cnt))

def combi(enemy_stone_count, edges, start):
    global ans

    if len(edges)>2 :
        return
    
    ans = max(ans, enemy_stone_count)

    for i in range(start, len(group)):
        cur_set = set(edges)
        
        for e in group[i][0]:
            cur_set.add(e)
        
        combi(enemy_stone_count+group[i][1], cur_set, i+1)

for i in range(N):
    for j in range(M):
        if board[i][j] == 2:
            bfs(i,j)

combi(0, set(), 0)

print(ans)