[Java] 백준 12869번 뮤탈리스크

SCV의 체력을 전부 0으로 만드는데 최소한의 공격 횟수를 구하는 문제입니다.

최대 3개의 SCV가 있으므로 가능한 경우는 다음과 같습니다.
1. [1, 3, 9]
2. [1, 9, 3]
3. [3, 1, 9]
4. [3, 9, 1]
5. [9, 1, 3]
6. [9, 3, 1]

위의 경우 모두 탐색해주었습니다.

0, 0, 0에서 한번의 공격으로 가능한 경우 입니다.
1, 3, 9
1, 9, 3
3, 1, 9
3, 9, 1
9, 1, 3
9, 3, 1

위의 값들을 정렬하면 전부 1, 3, 9가 됩니다.
SCV를 정렬해서 1, 3, 9가 되는지 확인하면 되므로 6가지의 경우의 수에 대해서 정렬을 해주어서 같은 경우는 visit배열을  통해서 방문처리를 하여 중복 방문을 없애주었습니다.

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = null;

    int n = Integer.parseInt(br.readLine());
    int result = 0;
    int[] arr = new int[3];
    int[][] calc = { { 1, 3, 9 }, { 1, 9, 3 }, { 3, 1, 9 }, { 3, 9, 1 }, { 9, 1, 3 }, { 9, 3, 1 } };
    boolean[][][] visit = new boolean[61][61][61];
    Queue<Data> q = new LinkedList<>();

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < n; ++i) {
      arr[i] = Integer.parseInt(st.nextToken());
    }

    Arrays.sort(arr);

    q.add(new Data(0, 0, 0, 0));

    int[] compare = new int[3];
    while (!q.isEmpty()) {
      int a = q.peek().a;
      int b = q.peek().b;
      int c = q.peek().c;
      int cnt = q.peek().cnt;
      q.poll();

      for (int i = 0; i < 6; ++i) {
        compare[0] = a + calc[i][0];
        compare[1] = b + calc[i][1];
        compare[2] = c + calc[i][2];

        compare[0] = compare[0] > 60 ? 60 : compare[0];
        compare[1] = compare[1] > 60 ? 60 : compare[1];
        compare[2] = compare[2] > 60 ? 60 : compare[2];

        Arrays.sort(compare);

        if (visit[compare[0]][compare[1]][compare[2]]) {
          continue;
        }

        visit[compare[0]][compare[1]][compare[2]] = true;

        q.add(new Data(compare[0], compare[1], compare[2], cnt + 1));

        if (compare[0] >= arr[0] && compare[1] >= arr[1] && compare[2] >= arr[2]) {
          result = cnt + 1;

          while (!q.isEmpty()) {
            q.poll();
          }
          break;
        }

      }
    }

    bw.write(result + "\n");
    bw.close();
  }

  public static class Data {
    int a;
    int b;
    int c;
    int cnt;

    public Data(int a, int b, int c, int cnt) {
      this.a = a;
      this.b = b;
      this.c = c;
      this.cnt = cnt;
    }
  }
}