[코드트리] 강력한 폭발 Python

폭탄이파괴시킨영역이

폭탄일경우를생각해야한다.

# n 입력
n = int(input())
# grid 입력
grid = [
    list(map(int, input().split()))
    for _ in range(n)
]
# 함수들
# in_range(x, y)
def in_range(x, y):
    return 0 <= x < n and 0 <= y < n

# get_destroyed_num(curr_grid)
def get_destroyed_num(curr_grid):

    # curr_grid를 돌면서
    for i in range(n):
        for j in range(n):
            
            # 1번 폭탄을 발견하면
            if curr_grid[i][j] == 1:
                for r in range(-2, 3):
                    # 범위 내에 있고, 폭탄이 아니면
                    if in_range(i+r, j) and not curr_grid[i+r][j]:
                        # 초토화
                        curr_grid[i+r][j] = 4
            
            # 2번 폭탄을 발견하면
            elif curr_grid[i][j] == 2:
                # dxs, dys
                dxs, dys = [-1, 1, 0, 0], [0, 0, -1, 1]
                for dx, dy in zip(dxs, dys):
                    nx, ny = i + dx, j + dy
                    # 범위 내에 있고 폭탄이 아니면
                    if in_range(nx, ny) and not curr_grid[nx][ny]:
                        # 초토화
                        curr_grid[nx][ny] = 4
            
            # 3번 폭탄을 발견하면
            elif curr_grid[i][j] == 3:
                # dxs, dys
                dxs, dys = [-1, -1, 1, 1], [-1, 1, 1, -1]
                for dx, dy in zip(dxs, dys):
                    nx, ny = i + dx, j + dy
                    # 범위 내에 있고, 폭탄이 아니면
                    if in_range(nx, ny) and not curr_grid[nx][ny]:
                        # 초토화
                        curr_grid[nx][ny] = 4
    
    # curr_destroyed_num
    curr_destroyed_num = 0

    # curr_grid를 돌면서
    for i in range(n):
        for j in range(n):
            # 초토화된 곳 또는 폭탄이 있으면
            if curr_grid[i][j]:
                # curr_destroyed_num에 추가
                curr_destroyed_num += 1

    # 반환
    return curr_destroyed_num

# simulate(bomb_list)
def simulate(bomb_list):

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

    # 현재 폭탄 리스트를
    for bomb in bomb_list:
        # temp_grid에 심어주기
        temp_grid[bomb[0]][bomb[1]] = bomb[2]
    
    # 반환
    return get_destroyed_num(temp_grid)

# make_comb(curr_idx)
def make_comb(curr_idx):

    global max_destroyed_num

    # 종료조건
    if curr_idx == bomb_cnt + 1:
        
        # 폭탄 번호 매겨주기
        for i in range(bomb_cnt):
            bomb_pos[i][2] = bomb_comb[i]

        # max_destroyed_num update
        max_destroyed_num = max(max_destroyed_num, simulate(bomb_pos))

        # 종료
        return
    
    for i in range(1, 3 + 1):
        bomb_comb.append(i)
        make_comb(curr_idx + 1)
        bomb_comb.pop()

# 설계
# bomb_cnt, bomb_pos, max_destroyed_num
bomb_cnt, bomb_pos, max_destroyed_num = 0, [], 0

# grid를 돌면서
for i in range(n):
    for j in range(n):
        # 폭탄이 있다면
        if grid[i][j]:
            # bomb_cnt 올려주고
            bomb_cnt += 1
            # bomb_pos에 등록 (x, y, 폭탄번호(미정))
            bomb_pos.append([i, j, 0])

# bomb_comb
bomb_comb = []

# 함수 호출
make_comb(1)

# 출력
print(max_destroyed_num)