백준 #12869 뮤탈리스크

문제 링크

[12869 뮤탈리스크]

문제 설명

최대 세마리의 SCV를 공격할 수 있는 뮤탈리스크가 있다. 첫번째 입힐 수 있는 데미지는 9, 두번째는 3, 세번째는 1이다. 60이하의 체력을 가진 SCV가 최대 3마리 주어질 때 최소 몇번의 공격으로 SCV를 처치할 수 있는지 구하는 문제

코드

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


def bfs():
    q = deque()
    q.append((arr[0], arr[1], arr[2]))
    while q:
        a, b, c = q.popleft()
        cnt = visited[a][b][c] + 1
        for x, y, z in mutal:
            na = max(0, a - x)
            nb = max(0, b - y)
            nc = max(0, c - z)
            if visited[na][nb][nc] > cnt:
                visited[na][nb][nc] = cnt
                q.append((na, nb, nc))

N = int(input())
arr = list(map(int, input().split()))
if len(arr) == 2:
    arr += [0]
elif len(arr) == 1:
    arr += [0, 0]

visited = [[[float("inf")] * 61 for _ in range(61)] for _ in range(61)]
visited[arr[0]][arr[1]][arr[2]] = 0
mutal = [[9, 3, 1], [9, 1, 3], [3, 9, 1], [3, 1, 9], [1, 9, 3], [1, 3, 9]]
bfs()
print(visited[0][0][0])

풀이

처음에는 그냥 체력이 가장 큰 SCV부터 공격하면 되는거 아니야? 라고 생각했었다. 근데 누굴 먼저 공격하느냐에 따라서 다음턴에 바로 끝낼 수도 있고 한턴을 더 써야할 수도 있다. 예를들어 12 10 4 의 체력을 생각해보자. 높은 체력을 먼저 공격한다 가정하면 12 10 4 -> 9 7 3 -> 0 4 2 -> 0 0 0 3턴을 써야한다 그런데 12 10 4 -> 3 9 1 > 0 0 0 단 2턴만에 끝낼 수 있다. 따라서 전부 탐색해보기로 했고 BFS를 이용해서 이미 방문한 적이 있는 체력같은 경우는 현재 들어갈 턴수가 작을 경우만 갱신 후에 큐에 넣어주었다. 마지막으로 체력이 0 0 0인 visited배열을 확인해서 출력해주면 끝!

예전에 물통 이라는 문제를 보고 어떻게 풀지 몰라서 안푼 기억이있다. 이번 문제도 그 문제랑 비슷한거같아서 일단 겁부터 먹고 시작 ㅎㅎ 다행히 잘 풀어냈다! 내일은 물통을 풀어보자!