[백트래킹] K개 중 하나를 N번 선택하기(Simple) / 강력한 폭발

문제링크

https://www.codetree.ai/missions/2/problems/strong-explosion?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• bomb_postion에 어떤 폭탄의 타입을 줘야하는가?
  
  • 예를 들어, bomb_position이 10곳이며 폭탄의 타입이 3개이므로 단순 for문으로 전수조사를 하기 위해서는 10중 for문이 필요하다. 즉, 폭탄의 위치에 따라서 for문의 수가 달라지므로 단순 for문을 돌리는 것으로는 해결하기 어렵다는 것을 알아야한다.
• 따라서 폭탄을 놓아야 하는 위치에 놓이게 될 폭탄 종류에 대한 모든 순열을 만들어서, 최대 영역을 구하도록 한다.
  • 폭탄의 종류를 뽑는데 특별한 조건이 없다. 예를 들어, 인접한 위치에 폭탄의 종류는 달라야한다 등등. 그러므로 폭탄의 종류에 대해서 전체 경우의 수를 뽑으면 되므로 simple버전이라고 할 수 있다.

2. 코드(Python)

# 내 풀이
def find_bomb_position(board):
    res = []
    for i in range(n):
        for j in range(n):
            if board[i][j] == 1:
                res.append((i, j))
    return res


def is_range(r, c):
    return 0 <= r < n and 0 <= c < n


def bomb_1(board, r, c):
    dirs = [(- 1, 0), (- 2, 0), (1, 0), (2, 0)]
    for dr, dc in dirs:
        nr, nc = r + dr, c + dc
        if is_range(nr, nc):
            board[nr][nc] = 1


def bomb_2(board, r, c):
    dirs = [(- 1, 0), (1, 0), (0, -1), (0, 1)]
    for dr, dc in dirs:
        nr, nc = r + dr, c + dc
        if is_range(nr, nc):
            board[nr][nc] = 1


def bomb_3(board, r, c):
    dirs = [(- 1, -1), (-1, 1), (1, -1), (1, 1)]
    for dr, dc in dirs:
        nr, nc = r + dr, c + dc
        if is_range(nr, nc):
            board[nr][nc] = 1


def bomb_board(board, bomb_number: list[int]):
    for (r, c), bomb in zip(bomb_list, bomb_number):
        if bomb == 1:
            bomb_1(board, r, c)
        elif bomb == 2:
            bomb_2(board, r, c)
        elif bomb == 3:
            bomb_3(board, r, c)
    
    cnt = 0
    for i in range(n):
        for j in range(n):
            if board[i][j] == 1:
                cnt += 1

    return cnt

from copy import deepcopy

def dfs(level, k):
    global max_region
    if level == k:
        new_board = deepcopy(board)
        max_region = max(max_region, bomb_board(new_board, ans))
        return

    for i in range(1, 4):
        ans.append(i)
        dfs(level + 1, k)
        ans.pop()


n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
bomb_position = find_bomb_position(board)
k = len(bomb_position)
max_region = 0
ans = []
dfs(0, k)
print(max_region)