[코드트리] 돌 잘 치우기 Python

# n, k, m 입력
n, k, m = map(int, input().split())
# grid 입력
grid = [
    list(map(int, input().split()))
    for _ in range(n)
]
# start_points
start_points = [
    tuple(map(int, input().split()))
    for _ in range(k)
]

# in_range(x, y)
def in_range(x, y):
    return 0 <= x < n and 0 <= y < n

# can_go(x, y)
def can_go(x, y):
    # 범위 내에 있고, 방문한 적 없고, 돌이 없으면 가능
    return in_range(x, y) and not visited[x][y] and not temp_grid[x][y]

# bfs()
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 can_go(nx, ny):
                q.append((nx, ny))
                visited[nx][ny] = True


# get_cnt(curr_del_stones)
def get_cnt(curr_del_stones):
    
    global visited, temp_grid

    # temp_grid
    temp_grid = [
        [0] * n
        for _ in range(n)
    ]

    for i in range(n):
        for j in range(n):
            temp_grid[i][j] = grid[i][j]

    # 제거할 돌 제거
    for del_pos in curr_del_stones:
        # unpacking
        x, y = del_pos
        # 바꿔주기
        temp_grid[x][y] = 0

    # 시작점들을 돌면서
    for point in start_points:
        # unpacking
        x, y = point
        x -= 1
        y -= 1

        # bfs
        q.append((x, y))
        visited[x][y] = True
        bfs()
    
    # curr_cnt
    curr_cnt = 0

    # visited를 돌면서
    for i in range(n):
        for j in range(n):
            # 방문한 점을 만나면
            if visited[i][j]:
                # curr_cnt에 추가
                curr_cnt += 1

    # visited 초기화
    visited = [
        [ False ] * n
        for _ in range(n)
    ]

    # 반환
    return curr_cnt

# simulate(curr_idx, cnt)
def simulate(curr_idx, cnt):
    # 전역 변수 선언
    global max_cnt
    
    # 종료 조건
    if curr_idx == stone_num:
        if cnt == m:
            # max_cnt update
            max_cnt = max(max_cnt, get_cnt(delete_stones))
        return
    
    delete_stones.append(stone_points[curr_idx])
    simulate(curr_idx + 1, cnt + 1)
    delete_stones.pop()
    simulate(curr_idx + 1, cnt)

# 설계
# stone_points
stone_points = []
for i in range(n):
    for j in range(n):
        # 돌을 발견하면
        if grid[i][j]:
            # stone_points에 추가
            stone_points.append((i, j))

# stone_num
stone_num = len(stone_points)

# max_cnt
max_cnt = 0

# delete_stones
delete_stones = []

# 큐 사용준비
from collections import deque
q = deque()

# visited
visited = [
    [ False ] * n
    for _ in range(n)
]

# m개의 돌 고르고 제거하여 최대 도달 가능 칸 update하기 
simulate(0, 0)

# 출력
print(max_cnt)