[python] 백준 12869 뮤탈리스크

1차 시도

from collections import deque
from itertools import permutations
N = int(input())
arr = list(map(int, input().split()))
attack = [9,3,1]
depth = 0

def BFS(arr):
    global depth
    q = deque()
    q.append(arr)
    while q:
        l = len(q.copy())
        for _ in range(l):
            this = q.popleft()
            if sum(this) == 0:
                return depth
            for p in permutations(attack[:N]):
                q.append([max(scv-a,0) for scv, a in zip(this,p)])

        depth +=1

print(BFS(arr))

시간초과, 메모리 초과

permutation 수행은 O(6) 이지만 BFS 탐색은 (60,60,60) 의 모든 체력이 0이 될 때까지 진행되어야 하므로 최대 타격 9를 기준으로 보아도 max depth가 약 21개이다 (정확히는 부수 타격으로 이미 SCV가 손상되어 있으므로 depth 가 더 적음)

O(6^21) 은 대략 O(N^2) 임.

6^15 = 4700억으로 시간 초과. Pypy3로 풀어도 메모리 초과임. 숫자 하나 당 1 byte 라고 해도 6^21 byte로 약 1GB byte 정도.

정답 코드

from collections import deque
from itertools import permutations

N = int(input())
inp = list(map(int, input().split()))
arr = [0, 0, 0]
for i in range(N):
    arr[i] = inp[i]

v = [[[0] * 64 for _ in range(64)] for _ in range(64)]
attack = [9, 3, 1]


def BFS(arr):
    q = deque()
    q.append(arr)
    while q:
        l = len(q.copy())
        for _ in range(l):
            this = q.popleft()
            if sum(this) == 0:
                return v[this[0]][this[1]][this[2]]
            for p in permutations(attack[:N]):
                hp = [max(scv - a, 0) for scv, a in zip(this, p)] + [0] * (3 - len(p))
                if not v[hp[0]][hp[1]][hp[2]]:
                    v[hp[0]][hp[1]][hp[2]] = v[this[0]][this[1]][this[2]] + 1
                    q.append(hp)


v[arr[0]][arr[1]][arr[2]] += 1
print(BFS(arr) - 1)

정답 코드는 BFS에서의 문제를 해결하기 위해서 visited를 사용하는 것임. visited를 사용하면 공간복잡도가 훨씬 줄어들 것임.

여기서는 3차원 배열을 사용하여 공간 복잡도를 줄여서 해결.