백준: 12869 뮤탈리스크

문제

12869번: 뮤탈리스크

 

문제 풀이

 뮤탈리스크는 한 번에 3마리의 SCV를 공격할 수 있다. 첫 번째 공격은 9, 두 번째 공격은 3, 세 번째 공격은 1로 체력을 감소시킬 때, 모든 SCV의 체력이 0이 되는 가장 빠른 경우의 공격 횟수를 반환하는 문제이다.

 

DFS를 통해서도 풀 수 있으며 문제를 풀기 위해 BFS를 통해 탐색을 진행하여 문제의 답을 찾았다.

• (9, 3, 1)로 공격 가능한 패턴을 `permutation`을 활용하여 구한다.
• BFS를 통해 공격 가능한 패턴만큼 가지를 확장해 나간다.
  • 이때, scv3의 체력이 가장 높은 상태로 정렬해서 나간다.
• 재방문을 막기 위해 `visited`를 3차원 배열로 체력의 크기만큼 만들어 방문 여부를 체크한다.
• scv들의 체력은 정렬된 상태이므로, 세 번째 scv의 체력이 0이 된다면 BFS 탐색을 종료한다.

 

코드

from sys import stdin
from itertools import permutations
from collections import deque


def bfs():
    q = deque([[*scv, 0]])

    while q:
        cur_state = q.popleft()

        # 정렬된 상태에서 체력이 큰 SCV의 체력이 없다면 종료.
        if cur_state[THREE] == 0:
            return cur_state[CNT]

        # 공격 가능한 경우의 수만큼 큐에 추가.
        for case in attack_case:
            next_scv = [0] * 3

            # visited에 방문 여부를 체크하기 위해 0보다 작은 경우 0으로 변환.
            for i in range(3):
                next_scv[i] = \
                    cur_state[i] - case[i] if cur_state[i] - case[i] > 0 else 0

            # 정렬된 상태로 큐에 추가.
            next_scv.sort()

            if not visited[next_scv[ONE]][next_scv[TWO]][next_scv[THREE]]:
                visited[next_scv[ONE]][next_scv[TWO]][next_scv[THREE]] = True
                q.append([*next_scv, cur_state[CNT] + 1])


if __name__ == '__main__':
    ONE, TWO, THREE, CNT = 0, 1, 2, 3
    n = int(stdin.readline())
    # n이 3보다 작을 경우, 0을 추가해주어 n이 1, 2인 경우 별도로 처리하지 않아도 됨.
    scv = sorted(list(map(int, stdin.readline().split())) + (3 - n) * [0])
    attack_case = list(permutations([9, 3, 1], 3))
    visited = [[[False] * 61 for _ in range(61)] for _ in range(61)]
    print(bfs())