[코드트리] Backtracking - 강력한 폭발

문제

코드트리 학습하기 - 알고리즘 입문 : Backtracking

• 강력한 폭발 (Python)
  https://www.codetree.ai/missions/2/problems/strong-explosion/description

코드 구현

# 1 : [0~i][j]
# 2 : 상하좌우
# 3 : 대각선

n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]

bomb_m = [[0 for _ in range(n)] for _ in range(n)]

d1 = [(-2, 0), (-1, 0), (1, 0), (2, 0)]    # 1번 폭탄의 피해 방향
d2 = [(-1, 0), (1, 0), (0, 1), (0, -1)]    # 2번 폭탄의 피해 방향
d3 = [(-1, -1), (-1, 1), (1, -1), (1, 1)]  # 3번 폭탄의 피해 방향

bomb_index = []

arr = []
ans = []

## bomb_m 초기화 함수
def init_bomb_m():
    bomb_m = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(len(bomb_index)):
        bomb_m[bomb_index[i][0]][bomb_index[i][1]] = 1
    return bomb_m

## 폭탄의 피해범위 구하기
def bomb_explosion(arr):
    # 변수 초기화
    bomb_m = init_bomb_m()
    count = len(arr)

    # 폭탄 종류에 맞춰서 각 폭탄이 존재하는 인덱스에 해당 폭탄 종류가 터졌을 때의 맵 상황 bomb_m에 기록하기 (0은 빈칸, 1은 피해입은칸)
    for b in range(len(arr)):
        bx = bomb_index[b][0]
        by = bomb_index[b][1]

        if (arr[b] == 1):       # 1번 폭탄
            for j in range(len(d1)):
                dx = d1[j][0]
                dy = d1[j][1]
                if (bx + dx < n and by + dy < n and bx + dx >= 0 and by + dy >= 0):
                    if (bomb_m[bx + dx][by + dy] == 0):
                        bomb_m[bx + dx][by + dy] = 1
                        count += 1

        if (arr[b] == 2):       # 2번 폭탄
            for j in range(len(d2)):
                dx = d2[j][0]
                dy = d2[j][1]
                if (bx + dx < n and by + dy < n and bx + dx >= 0 and by + dy >= 0):
                    if (bomb_m[bx + dx][by + dy] == 0):
                        bomb_m[bx + dx][by + dy] = 1
                        count += 1

        if (arr[b] == 3):       # 3번 폭탄
            for j in range(len(d3)):
                dx = d3[j][0]
                dy = d3[j][1]
                if (bx + dx < n and by + dy < n and bx + dx >= 0 and by + dy >= 0):
                    if (bomb_m[bx + dx][by + dy] == 0):
                        bomb_m[bx + dx][by + dy] = 1
                        count += 1

    ans.append(count)


## 폭탄의 종류를 결정해서 조합을 만듦
def get_bomb_list(num):
    if (num == count_b):
        bomb_explosion(arr)  # 만들어진 폭탄의 피해 규모 확인
        return

    for i in range(1, 4):  # 폭탄은 1,2,3 세 종류
        arr.append(i)
        get_bomb_list(num + 1)
        arr.pop()
    return


### main 실행 부분
count_b = 0
for i in range(n):
    for j in range(n):
        if (matrix[i][j] == 1):
            count_b += 1  # 폭탄의 개수 카운트
            bomb_index.append((i, j))  # 폭탄의 인덱스 저장
            bomb_m[i][j] = 1

get_bomb_list(0)

# print(ans)
print(max(ans))

풀이

• 계속 해왔던 Backtracking 문제처럼 구조를 잡아준다. → get_bomb_list

• 우선 Backtracking에 들어가기 전에 폭탄의 위치와 인덱스를 저장해준다.

• 이후 폭탄의 종류에 따른 조합을 Backtracking으로 get_bomb_list 에서 만들어준다.

• 만약 맵에 있는 폭탄의 개수만큼 조합이 만들어지면 → 해당 폭탄 조합의 피해 규모를 확인하기 위해 bomb_explosion 함수로 이동하여 검사한다.

• bomb_explosion 함수에서는 각 폭탄의 종류에 맞춰서 맵의 인덱스 내부의 피해 규모를 저장해준다.

• 그 다음 조합의 검사를 위해서는 임시 맵을 초기화해준다. (init_bomb_m)

• 모든 조합의 폭탄 피해 규모를 저장한 배열 중 최댓값이 정답으로 출력된다.

• 시간을 잡아먹었던 점 :

  • 배열1 = 배열2 로 할당해놓고, 배열1을 변경하면 배열2도 갑자기 같이 변경되는 점에서 거의 30-40분 애먹었다…
    • https://black-hair.tistory.com/49
      이걸 참고해보니 실제 리스트는 1개로 선언되어있고 포인터 형식으로 지정한거라서 같이 변동된다고 한다.
    • 따라서 새로 선언 + 새로 초기화 를 통해 완전히 분리해주어야 한다 !!! → init_bomb_m 함수 생성 계기
  • 알고보니 1번 폭탄도 동일하게 위로 4칸이 터지는거였는데 해당 n * n 배열의 높이만큼 터지는줄 알았다 …

• 수정해보기 :

  • 폭탄이 터지는 것을 기록하는 과정에서 폭탄 종류만 다르지 피해 범위를 구하는건 중복 코드가 존재하기 때문에 이를 깔끔하게 정리해줄 수 있을 것 같다.
  • 코드가 짧아지면 함수 → 함수를 또 타고 들어가서 구하지 않고 그냥 한 함수로 구현해도 괜찮을 것 같다.
    (초기화 문제가 해결될수도)