[프로그래머스] 블록 게임 / Java

문제주소 :programmers.co.kr/learn/courses/30/lessons/42894#

코딩테스트 연습 - 블록 게임

---

<문제 설명>

문제 설명

블록게임

프렌즈 블록이라는 신규 게임이 출시되었고, 어마어마한 상금이 걸린 이벤트 대회가 개최 되었다.

이 대회는 사람을 대신해서 플레이할 프로그램으로 참가해도 된다는 규정이 있어서, 게임 실력이 형편없는 프로도는 프로그램을 만들어서 참가하기로 결심하고 개발을 시작하였다.

프로도가 우승할 수 있도록 도와서 빠르고 정확한 프로그램을 작성해 보자.

게임규칙

아래 그림과 같이 1×1 크기의 블록을 이어 붙여 만든 3 종류의 블록을 회전해서 총 12가지 모양의 블록을 만들 수 있다.

1 x 1 크기의 정사각형으로 이루어진 N x N 크기의 보드 위에 이 블록들이 배치된 채로 게임이 시작된다. (보드 위에 놓인 블록은 회전할 수 없다). 모든 블록은 블록을 구성하는 사각형들이 정확히 보드 위의 사각형에 맞도록 놓여있으며, 선 위에 걸치거나 보드를 벗어나게 놓여있는 경우는 없다.

플레이어는 위쪽에서 1 x 1 크기의 검은 블록을 떨어뜨려 쌓을 수 있다. 검은 블록은 항상 맵의 한 칸에 꽉 차게 떨어뜨려야 하며, 줄에 걸치면 안된다.
이때, 검은 블록과 기존에 놓인 블록을 합해 속이 꽉 채워진 직사각형을 만들 수 있다면 그 블록을 없앨 수 있다.

예를 들어 검은 블록을 떨어뜨려 아래와 같이 만들 경우 주황색 블록을 없앨 수 있다.

빨간 블록을 가로막던 주황색 블록이 없어졌으므로 다음과 같이 빨간 블록도 없앨 수 있다.

그러나 다른 블록들은 검은 블록을 떨어뜨려 직사각형으로 만들 수 없기 때문에 없앨 수 없다.

따라서 위 예시에서 없앨 수 있는 블록은 최대 2개이다.

보드 위에 놓인 블록의 상태가 담긴 2차원 배열 board가 주어질 때, 검은 블록을 떨어뜨려 없앨 수 있는 블록 개수의 최댓값을 구하라.

제한사항

• board는 블록의 상태가 들어있는 N x N 크기 2차원 배열이다.
  • N은 4 이상 50 이하다.
• board의 각 행의 원소는 0 이상 200 이하의 자연수이다.
  • 0 은 빈 칸을 나타낸다.
  • board에 놓여있는 각 블록은 숫자를 이용해 표현한다.
  • 잘못된 블록 모양이 주어지는 경우는 없다.
  • 모양에 관계 없이 서로 다른 블록은 서로 다른 숫자로 표현된다.
  • 예를 들어 문제에 주어진 예시의 경우 다음과 같이 주어진다.

---

입출력 예

board                                                                  result

[[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]]

2

입출력 예 설명

입출력 예 #1
문제에 주어진 예시와 같음

 

<풀이법>

▒ 한줄 개념: 구현 ▒ 

구현적인 능력이 요구되는 문제이다. 크게 이해가 어려운 문제가 아니라서, 스텝 바이 스텝으로 풀었다.

 

<<풀이법 간단 요약>>

1. 제거할 수 있는 블록의 종류를 확인한다.

2. 반복문을 돌면서 마주친 블록이 ROW인지, COLUMN인지 확인한다.

3-1. ROW일 경우 ROW 체크 함수를 통해 삭제 가능 여부를 파악한다. 삭제 가능일 경우 삭제하고, true 반환

3-2. COLUMN일 경우 COLUMN 체크 함수를 통해 삭제 가능 여부를 파악한다. 삭제 가능일 경우 삭제하고, true 반환

4. 3-1, 3-2번의 결과가 true이면 answer++.

5. 최종 answer 반환.

 

---

1. 제거할 수 있는 블록의 종류를 확인한다.

여러 블록의 종류를 보고, 위에서 블록을 내려서 직사각형을 만들 수 있는 블록을 확인했다. 사진과 같이 5가지의 종류의 블록만 조건을 만족함을 알 수 있다.

연두색 네모가 제거할 수 있는 블록

 

2. 반복문을 돌면서 마주친 블록이 ROW인지, COLUMN인지 확인한다.

5가지 종류의 블록을 탐색의 편의를 위해 ROW와 COLUMN으로 구분하였다. 처음엔 true, false로 구분하였으나, ROW와 COLUMN이 아닌 그냥 튀어나온 부분일수도 있으므로, int형 값으로 설정하였다. 왼쪽 위에서부터 오른쪽 아래로 내려오며 반복문을 돌고, 해당 블럭이 ROW 형 블록인지 COLUMN형 블록인지 확인한다.

이 경우, 해당 블록에서 동일한 세개가 나타나는 가장 왼쪽, 아래 지점에서 정상적인 판별이 이루어지도록 함수를 짰다. 어차피 위에서부터 제거하면서 내려오기 때문에, 왼쪽 아래에서 블록의 종류를 판단하면 될 것이라 생각했다.

블록 분류와 체크 포인트

 

3. ROW / COLUMN 일 경우 ROW / COLUMN 체크 함수를 통해 삭제 가능 여부를 파악한다. 삭제 가능일 경우 삭제하고, true 반환

각 블록에 대해 삭제 가능한 블록인지 판단하는 것은 위의 분류했던 형태를 가지고 단순 조건문을 이용해 파악해주었다. 어차피 ROW 형이면 해당 위치에서 왼쪽 세개는 동일하다는 것이 체크 되었고, COLUMN 형이면 위로 세개는 동일하다는 것이 체크 되었으니, 툭 튀어나온 부분만 체크해주면 되었다. 따라서 ROW 체크 함수에서는 3가지 조건문이, COLUMN 체크 함수에서는 2가지 조건문을 구현했다. 여기까지가 구체적인 형태에 대한 파악이었다. ROW 형이면 3가지 중 어떤 ROW인지, COLUMN 형이면 두가지 중 어떤 COLUMN인지 판단했다.

그 후 검은 블록이 정상적으로 내려올 수 있는지, 즉 튀어나온 부분이 아닌 나머지 부분에 대해서 위쪽이 전부 비었는지 판단해주었고, 만약 빈 공간들에 대해 위쪽 모든 부분이 똑같이 비었다면 해당 블록은 삭제될 수 있는 블록이므로 삭제를 진행하고 true를 반환해준다. 

 

 

4. 3번의 결과가 true이면 answer++.  / 5. 최종 answer 반환.

위 과정을 통해 나온 boolean 값을 토대로 최종 값을 만들어 반환해준다.

 

 

<코드(Java)>

class Solution {
    int[][] board;
    int n;
    int ROW = 201, COLUMN = 202;
    public int solution(int[][] board) {
        int answer = 0;
        this.n = board.length;
        this.board = board;
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] != 0){
                    int direction = checkDirection(i,j);
                    if(direction == COLUMN && checkColumn(i, j)){
                        answer++;
                    }
                    if(direction == ROW && checkRow(i, j)){
                        answer++;
                    }
                }
            }
        }
        return answer;
    }
    
    int checkDirection(int i, int j){
        int num = board[i][j];
        if(i-2 >= 0 && board[i-1][j] == num && board[i-2][j] == num)
            return COLUMN;
        if(j+2 < n && board[i][j+1] == num && board[i][j+2] == num)
            return ROW;
        
        else return -1;
    }
    
    boolean checkColumn(int i, int j){
        int num = board[i][j];
        if(j-1 >= 0){
            if(board[i][j-1] == num && board[i-1][j-1] == 0 && board[i-2][j-1] == 0){
                if(checkUpper(i-2, j-1)){
                    board[i][j-1] = 0;
                    cleanColumn(i, j);
                    return true;
                } 
                else return false;
            }
        }
        
        if(j+1 < n){
            if(board[i][j+1] == num && board[i-1][j+1] == 0 && board[i-2][j+1] == 0){
                if(checkUpper(i-2, j+1)){
                    board[i][j+1] = 0;
                    cleanColumn(i, j);
                    return true;
                }
                else return false;
            }
        }
        
        return false;
    }
    
    boolean checkRow(int i, int j){
        int num = board[i][j];
        if(i-1 >= 0){
            if(board[i-1][j] == num && board[i-1][j+1] == 0 && board[i-1][j+2] == 0){
                if(checkUpper(i-1, j+1) && checkUpper(i-1, j+2)){
                    board[i-1][j] = 0;
                    cleanRow(i,j);
                    return true;
                }
            }
            if(board[i-1][j] == 0 && board[i-1][j+1] == num && board[i-1][j+2] == 0){
                if(checkUpper(i-1, j) && checkUpper(i-1, j+2)){
                    board[i-1][j+1] = 0;
                    cleanRow(i,j);
                    return true;
                }
            }
            if(board[i-1][j] == 0 && board[i-1][j+1] == 0 && board[i-1][j+2] == num){
                if(checkUpper(i-1, j) && checkUpper(i-1, j+1)){
                    board[i-1][j+2] = 0;
                    cleanRow(i,j);
                    return true;
                }
            }
        }
        
        return false;
    }
    
    boolean checkUpper(int i, int j){
        for(int k = i; k >= 0; k--){
            if(board[k][j] != 0) return false;
        }
        return true;
    }
    
    void cleanColumn(int i, int j){
        for(int k = 0; k < 3; k++){
            board[i-k][j] = 0;
        }
    }
    
    void cleanRow(int i, int j){
        for(int k = 0; k < 3; k++){
            board[i][j+k] = 0;
        }
    }
}

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest