백준 알고리즘 12869번 뮤탈리스크 풀이 With Python

문제 링크: www.acmicpc.net/problem/12869

12869번: 뮤탈리스크

저는 SCV의 개수에 따라 CASE분류를 통하여 문제를 해결하였습니다. 먼저 SCV수가 1마리일 경우 SCV체력을 9로 나누어 나머지가 0일 경우 몫을 출력하고 아닐 경우 몫+1의 값을 출력하였습니다. SCV가 2마리 이상일 경우에는 DFS(깊이 우선 탐색)으로 문제를 해결하였습니다. 만약 현재 최소의 횟수보다 같거나 높아진다면 분기하지 않는 백 트레킹을 사용하였고, 한 번만 탐색한 것을 체크하기 위해 SCV의 체력을 정렬하여 visit이라는 DICTIONARY 구조에 체크하였습니다. 소스코드는 아래와 같습니다.

 

import sys
from copy import deepcopy

n = int(sys.stdin.readline())
scv = list(map(int, sys.stdin.readline().split()))
scv.sort()
number = len(scv)
visit = {}
answer = float('inf')

# 답이 되는지를 CHECK하는 함수
def check(list1):
    for i in list1:
        if i > 0:
            return False
    return True

# SCV가 2마리일 경우 답을 찾는 함수
def solution2(scv, count):
    global answer
    scv.sort()
    if answer <= count or visit.get((scv[0], scv[1])) is not None:
        return
    elif check(scv) and answer > count:
        answer = count
        return
    visit[(scv[0], scv[1])] = 1
    temp = deepcopy(scv)
    temp[0] -= 9
    temp[1] -= 3
    solution2(temp, count + 1)
    temp[0] = scv[0]
    temp[1] = scv[1]
    temp[0] -= 3
    temp[1] -= 9
    solution2(temp, count + 1)

# SCV가 3마리일 경우 답을 찾는 함수
def solution3(scv, count):
    global answer
    scv.sort()
    if answer <= count or visit.get((scv[0], scv[1], scv[2])) is not None:
        return
    elif check(scv) and answer > count:
        answer = count
        return
    visit[(scv[0], scv[1], scv[2])] = 1
    temp = deepcopy(scv)
    temp[0] -= 9
    temp[1] -= 3
    temp[2] -= 1
    solution3(temp, count + 1)
    temp[0] = scv[0]
    temp[1] = scv[1]
    temp[2] = scv[2]
    temp[0] -= 9
    temp[1] -= 1
    temp[2] -= 3
    solution3(temp, count + 1)
    temp[0] = scv[0]
    temp[1] = scv[1]
    temp[2] = scv[2]
    temp[0] -= 3
    temp[1] -= 9
    temp[2] -= 1

    solution3(temp, count + 1)
    temp[0] = scv[0]
    temp[1] = scv[1]
    temp[2] = scv[2]
    temp[0] -= 3
    temp[1] -= 1
    temp[2] -= 9

    solution3(temp, count + 1)
    temp[0] = scv[0]
    temp[1] = scv[1]
    temp[2] = scv[2]
    temp[0] -= 1
    temp[1] -= 3
    temp[2] -= 9

    solution3(temp, count + 1)
    temp[0] = scv[0]
    temp[1] = scv[1]
    temp[2] = scv[2]
    temp[0] -= 1
    temp[1] -= 9
    temp[2] -= 3
    solution3(temp, count + 1)


if number == 1:
    if scv[0] % 9 == 0:
        answer = scv[0] // 9
    else:
        answer = scv[0] // 9 + 1
elif number == 2:
    solution2(scv, 0)
else:
    solution3(scv, 0)
print(answer)

코드에 대해 질문이 있으시면 댓글을 남겨주시면 답변드리겠습니다. 감사합니다.