[Python/BOJ] 12869. 뮤탈리스크

https://www.acmicpc.net/problem/12869

 

문제

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.

각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.

뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.

1. 첫 번째로 공격받는 SCV는 체력 9를 잃는다.
2. 두 번째로 공격받는 SCV는 체력 3을 잃는다.
3. 세 번째로 공격받는 SCV는 체력 1을 잃는다.

SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.

남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 SCV의 수 N (1 ≤ N ≤ 3)이 주어진다. 둘째 줄에는 SCV N개의 체력이 주어진다. 체력은 60보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 SCV를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

풀이

Code

import sys
from collections import deque
from itertools import permutations
input = sys.stdin.readline

# 1. BFS 함수 정의
def bfs():
    # 1-1. 큐 생성 후 (scv 체력, 초기 공격 횟수) 정보 삽입
    queue = deque([(scv_hp, 0)])
    # 1-2.
    while queue:
        # 1-2-1. 체력, 공격 횟수 반환
        hp, cnt = queue.popleft()
        # 1-2-2.
        for power in powers:
            # 공격 후 잔여 HP 계산
            x, y, z = [scv_hp-p if scv_hp-p > 0 else 0 for scv_hp, p in zip(hp, power)]
            # 모든 SCV가 파괴된 경우
            if x == y == z == 0 :
                # 최소 공격 횟수 반환
                return cnt + 1
            # 잔여 HP가 구해진 적이 없는 경우
            if not checked[x][y][z]:
                # 잔여 HP 체크 처리
                checked[x][y][z] = True
                # 큐에 (잔여 HP, 공격 횟수) 삽입
                queue.append(([x, y, z], cnt+1))

N = int(input())
scv_hp = list(map(int, input().split())) + [0 for _ in range(3-N)]

# 2. SCV HP 계산 여부 리스트 생성 및 초기 설정
checked = [
    [
        [False for _ in range(61)]
        for _ in range(61)
    ]
    for _ in range(61)
]
checked[scv_hp[0]][scv_hp[1]][scv_hp[2]] = True
# 3. 뮤탈리스크 공격에 따른 공격력 순열 생성
powers = list(permutations((9, 3, 1)))
# 4. 최소 공격 횟수 출력
print(bfs())