[코드트리 조별과제] BFS - 돌 잘 치우기

from collections import deque

ans = 0
n, k, m = map(int, input().split())
mat = []
visited = [[False for _ in range(n)] for _ in range(n)]
for _ in range(n):
    mat.append([int(x) for x in input().split()])

s_pos = []
for _ in range(k):
    r, c = map(int, input().split())
    s_pos.append((r - 1, c - 1))

stone_pos = [(i, j) for i in range(n) for j in range(n) if mat[i][j] == 1]
selected_stones = []
q = deque()


def bfs():
    while q:
        x, y = q.popleft()
        dxs, dys = [1, -1, 0, 0], [0, 0, 1, -1]
        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and not mat[nx][ny] and not visited[nx][ny]:
                q.append((nx, ny))
                visited[nx][ny] = True


def calc():
    for x, y in selected_stones:
        mat[x][y] = 0
    for i in range(n):
        for j in range(n):
            visited[i][j] = False
    for x, y in s_pos:
        q.append((x, y))
        visited[x][y] = True
    bfs()
    for x, y in selected_stones:
        mat[x][y] = 1
    cnt = 0
    for i in range(n):
        for j in range(n):
            if visited[i][j]:
                cnt += 1
    return cnt


def find_max(idx, cnt):
    global ans
    if idx == len(stone_pos):
        if cnt == m:
            ans = max(ans, calc())
        return

    selected_stones.append(stone_pos[idx])
    find_max(idx + 1, cnt + 1)
    selected_stones.pop()
    find_max(idx + 1, cnt)


find_max(0, 0)
print(ans)

문제를 푸는데 실패했다.

백트레킹을 한다는 아이디어는 떠올렸지만, 돌을 만날 때 마다 재귀하는 방법을 고민하다가 아무리 생각해도 주어진 시간 복잡도를 만족시킬 수 없을것 같아 포기했다. 결국 확신이 없었다.

돌 중 2개를 선택하는 경우의 수를 따져나가는 방법이 맞았다!