[Codetree] 강력한 폭발 Python

https://www.codetree.ai/missions/2/problems/strong-explosion/description

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

 

❗풀이 방법

1. 백트레킹을 사용하여 폭파 지점의 개수만큼 1, 2, 3에서 중복을 허용하지 않고 뽑기

2. 폭파 지점의 개수만큼 리스트가 채워졌다면 해당 경우를 가지고 어떤 점이 폭파되는지 확인

3. 폭파 종류는 3개이므로 각각의 경우에 맞춰서 각 경우에 터지는 위치를 그래프에서 확인

4. 그래프에서 폭파되는 총 개수를 세어서 리턴

5. 그래프는 원래 맨 처음의 그래프로 원상복구

6. 폭파된 경우에서 가장 max인 경우로 값을 업데이트

 

 

❗코드

import sys
import copy

input = sys.stdin.readline

n = int(input())

graph = []
spot = []
result = []
answer = []
num = [1, 2, 3]  
cnt = 0

for i in range(n):
    temp = list(map(int, input().rstrip().split(" ")))
    graph.append(temp)

    for j in range(n):
        if temp[j] == 1:
            spot.append([i, j])

spot_len = len(spot)



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


def bomb(answer):
    cnt = 0
	
    # 타입에 따라 폭파 위치 표시
    for type, point in zip(answer, spot):
        i = point[0]
        j = point[1]

        if type == 1:
            if in_range(i - 2, j): graph[i - 2][j] = 1
            if in_range(i - 1, j): graph[i - 1][j] = 1
            if in_range(i + 1, j): graph[i + 1][j] = 1
            if in_range(i + 2, j): graph[i + 2][j] = 1

        elif type == 2:
            if in_range(i - 1, j): graph[i - 1][j] = 1
            if in_range(i + 1, j): graph[i + 1][j] = 1
            if in_range(i, j - 1): graph[i][j - 1] = 1
            if in_range(i, j + 1): graph[i][j + 1] = 1

        elif type == 3:
            if in_range(i - 1, j - 1): graph[i - 1][j - 1] = 1
            if in_range(i + 1, j - 1): graph[i + 1][j - 1] = 1
            if in_range(i - 1, j + 1): graph[i - 1][j + 1] = 1
            if in_range(i + 1, j + 1): graph[i + 1][j + 1] = 1
	
    # 폭파 지점 개수 
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 1:
                cnt += 1

    # 원상복구
    for i in range(n):
        for j in range(n):
            if [i, j] not in spot:
                graph[i][j] = 0

    return cnt


def backtrack(dep):
    global cnt

    if dep == spot_len:
        temp = copy.deepcopy(answer)
        cnt = max(cnt, bomb(temp))
        return

    for i in range(3):
        answer.append(num[i])
        backtrack(dep + 1)
        answer.pop()



backtrack(0)

print(cnt)