크레인 인형뽑기(카카오)

게임개발자인 죠르디는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다.
죠르디는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려 고 합니다.

게임 화면은 1 x 1 크기의 칸들로 이루어진 N x N 크기의 정사각 격자이며 위쪽에는 크레인 이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 5 x 5 크기의 예시입니다). 각 격자 칸에 는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 1 x 1 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인 형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 됩 니다. 다음 그림은 [1번, 5번, 3번] 위치에서 순서대로 인형을 집어 올려 바구니에 담은 모습 입니다.

 

만약 같은 모양의 인형 두 개가 바구니에 연속해서 쌓이게 되면 두 인형은 터뜨려지면서 바구 니에서 사라지게 됩니다. 위 상태에서 이어서 [5번] 위치에서 인형을 집어 바구니에 쌓으면 같은 모양 인형 두 개가 없어집니다.

크레인 작동 시 인형이 집어지지 않는 경우는 없으나 만약 인형이 없는 곳에서 크레인을 작동 시키는 경우에는 아무런 일도 일어나지 않습니다. 또한 바구니는 모든 인형이 들어갈 수 있을 만큼 충분히 크다고 가정합니다. (그림에서는 화면표시 제약으로 5칸만으로 표현하였음)

게임 화면의 격자의 상태가 담긴 2차원 배열 board와 인형을 집기 위해 크레인을 작동시킨 위 치가 담긴 배열 moves가 매개변수로 주어질 때, 크레인을 모두 작동시킨 후 터트려져 사라진 인형의 개수를 구하는 프로그램을 작성하세요.

 

▣ 입력설명
첫 줄에 자연수 N(5<=N<=30)이 주어집니다.
두 번째 줄부터 N*N board 배열이 주어집니다.
board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
0은 빈 칸을 나타냅니다.
1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나 타냅니다.
board배열이 끝난 다음줄에 moves 배열의 길이 M이 주어집니다.
마지막 줄에는 moves 배열이 주어집니다.
moves 배열의 크기는 1 이상 1,000 이하입니다.
moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.

▣ 출력설명
첫 줄에 터트려져 사라진 인형의 개수를 출력합니다.

▣ 입력예제 1

5

00000

00103

02501

42442

35131

8

15351214

▣ 출력예제 1

4

public static void main(String[] args) {
    // 게임판(인형별 번호)
    int[][] arr = new int[][]{
            {0,0,0,0,0},
            {0,0,1,0,3},
            {0,2,5,0,1},
            {4,2,4,4,2},
            {3,5,1,3,1}
    };

    // 열 선택 정보 (시작 1)
    int[] moveArr = new int[]{1,5,3,5,1,2,1,4};

    int solution = solution(arr, moveArr);

    System.out.println(solution);
}

private static int solution(int[][] arr, int[] moveArr) {
    List<Integer> basket = new ArrayList<>();
    int bubbleCnt = 0;

    for (int m : moveArr) {
        // 바스켓으로 이동 및 0처리
        moveToBasket(arr, basket, m);

        // 바스켓 내용물 출력
//            printBasket(basket);

        // 버블 처리
        bubbleCnt += doBubble(basket);
    }

    // 터진 인형수는 버블수 * 2
    return bubbleCnt * 2;
}

/**
 * 바스켓으로 이동
 * @param arr : 게임판
 * @param basket : 바스켓
 * @param m : 이동시킬 열 위치(시작 1)
 */
private static void moveToBasket(int[][] arr, List<Integer> basket, int m) {
    int temp = 0;
    // 게임판 인형 꺼내고 0으로 치환
    for(int i = 0; i < arr.length ; i++){
        temp = arr[i][m -1];
        if(arr[i][m -1] != 0){
            // 바스켓 마지막에 추가하기
            basket.add(temp);
            arr[i][m -1] = 0;
            break;
        }
    }
}

/**
 * 바스켓 쌓을 때마다 버블이 존재하지 않을때 까지 버블 검사
 * @param basket : 바스켓
 * @return : 버블 수
 */
private static int doBubble(List<Integer> basket) {
    int bubbleCnt = 0;
    boolean hasBubble = false;

    // 연속 버블 검사
    while (basket.size() >= 2) {
        hasBubble = false;

        for (int i = 0; i < basket.size() - 1; i++) {
            if(basket.get(i).equals(basket.get(i + 1))){
                bubbleCnt += 1;
                // 터진 인형 제거
                basket.remove(i+1);
                basket.remove(i);
                hasBubble = true;
                break;
            }
        }

        // 버블된 이력이 없으면 종료
        if(!hasBubble){
            break;
        }
    }
    return bubbleCnt;
}

/**
 * 바스켓 내용 출력
 * @param basket
 */
private static void printBasket(List<Integer> basket) {
    for (Integer integer : basket) {
        System.out.print(integer);
    }
    System.out.println("");
}