12869번 - 뮤탈리스크(bfs)

문제:

 

풀이:

scv의 체력이 주어져 있고, 뮤탈의 공격 방식도 정해져있다.

그렇다면, 모든 scv의 체력이 다 닳을때까지 뮤탈이 여러 방식으로 공격해보면 될 것이다.

자, 가능한 모든 경우의 수로 한대씩 때려보자.

위와 같은 결과가 나올 것이다.

만약 그 다음에도 한번씩 때려보면 6 x 6의 경우의 수가 나올 것이고, scv가 모두 죽는 경우의 수에 도달할 것이다.

위 그림을 보면, bfs를 사용하고 있다는 것을 알아볼 수 있을 것이다.

중복이 일어나지 않도록 visited 배열을 만들어 코드를 작성하면 쉽게 풀 수 있을 것이다.

 

1. 뮤탈의 공격 순번을 미리 저장해 놓는다.
   bfs를 위한 visited 배열은 3차원 배열로 저장해 놓을 것이다.
   

   int[][] attack = {{9, 3, 1}, {9, 1, 3},
           {3, 9, 1}, {3, 1, 9},
           {1, 9, 3}, {1, 3, 9}};
   boolean[][][] visited;

2. queue에 처음 scv들의 체력을 입력받고, visited 배열에 기록해 놓는다.
   

   int[] input = new int[4];
   for (int i = 0; i < N; i++) {
       input[i] = sc.nextInt();
   }
   sort(input);
   visited[input[0]][input[1]][input[2]] = true;
   queue.add(input);

3. 이후 아래 메서드를 통해 가장 빨리 scv를 모두 죽일 수 있는 방법을 구한다.
   

   static int bfs() {
       while (!queue.isEmpty()) {
           int[] temp = queue.poll();
   
           for (int i = 0; i < 6; i++) {
               int[] arr = new int[4];
               arr[0] = scv(temp[0], attack[i][0]);
               arr[1] = scv(temp[1], attack[i][1]);
               arr[2] = scv(temp[2], attack[i][2]);
               arr[3] = temp[3] + 1;
   
               if (arr[0] == 0 && arr[1] == 0 && arr[2] == 0) {
                   return arr[3];
               }
   
               sort(arr);
   
               if (!visited[arr[0]][arr[1]][arr[2]]) {
                   queue.add(arr);
                   visited[arr[0]][arr[1]][arr[2]] = true;
               }
           }
       }
       return 0;
   }

   
   
   1. queue에서 지금 scv의 체력을 가져온다.
   2. 뮤탈이 공격할 수 있는 경우의 수만큼 scv들을 공격해 체력을 갱신한다. 또한 arr[3]에 공격횟수를 갱신해준다.
      1. 만약 모든 체력이 0이라면, arr[3]에 저장되어 있는 공격 횟수를 반환한다.
      2. scv 3마리의 체력을 정렬해준다.
      3. 만약 해당 체력이 기록되어 있지 않은 체력이라면, queue에 scv들의 체력과 공격횟수를 저장한다.
         또한 해당 체력을 기록해 놓는다. 

 

전체코드:

import java.util.*;

public class Main {
    static int N;
    static Queue<int[]> queue;
    static int[][] attack = {{9, 3, 1}, {9, 1, 3},
            {3, 9, 1}, {3, 1, 9},
            {1, 9, 3}, {1, 3, 9}};
    static boolean[][][] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        queue = new LinkedList<>();
        visited = new boolean[61][61][61];

        int[] input = new int[4];
        for (int i = 0; i < N; i++) {
            input[i] = sc.nextInt();
        }
        sort(input);
        visited[input[0]][input[1]][input[2]] = true;
        queue.add(input);

        System.out.println(bfs());
    }

    static int bfs() {
        while (!queue.isEmpty()) {
            int[] temp = queue.poll();

            for (int i = 0; i < 6; i++) {
                int[] arr = new int[4];
                arr[0] = scv(temp[0], attack[i][0]);
                arr[1] = scv(temp[1], attack[i][1]);
                arr[2] = scv(temp[2], attack[i][2]);
                arr[3] = temp[3] + 1;

                if (arr[0] == 0 && arr[1] == 0 && arr[2] == 0) {
                    return arr[3];
                }

                sort(arr);

                if (!visited[arr[0]][arr[1]][arr[2]]) {
                    queue.add(arr);
                    visited[arr[0]][arr[1]][arr[2]] = true;
                }
            }
        }
        return 0;
    }

    static int scv(int scv, int attack) {
        if (scv > attack) {
            return scv - attack;
        } else {
            return 0;
        }
    }

    static void sort(int[] arr) {
        Integer[] arrCopy = {arr[0], arr[1], arr[2]};
        Arrays.sort(arrCopy, Collections.reverseOrder());
        arr[0] = arrCopy[0];
        arr[1] = arrCopy[1];
        arr[2] = arrCopy[2];
    }
}

scv 메서드는 뮤탈의 공격 이후 남는 체력을 갱신해주는 메서드이다.

sort는 scv의 체력을 역순으로 정렬해주며, 중복을 방지하기 위해 사용하는 메서드이다.

 

시행착오:

누군가의 도움 없이 알고리즘을 작성하다보니, 클래스명도 내맘대로 하고, static 변수를 너무 남발하고 있었다.

'무분별한 static의 사용은 메모리 유수(Leak)의 원인이 된다. 프로그램 종료 시점에 메모리를 반환하는 속성이 있어 GC(Garbage collection) 대상이 아니기 때문이다. 재사용성이 떨어진다.'

분명 이전 객체지향프로그래밍 시간에 들었던 내용이다.

static은 매우 편리하긴 하지만, 혼자 알고리즘을 푸는것에 있어서만 편리하고, 나쁜 버릇이 들게 될 것 같다.

앞으로 static 변수를 지양하고, 클래스명도 블로그에서는 영문으로 표기해야겠다.