알고리즘 공부/구현 , 시뮬레이션

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

kdhoooon 2021. 7. 29. 17:10

문제

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

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

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

게임규칙

아래 그림과 같이 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.  지울 수 있는 도형을 먼저 찾는다. 아래 그림에서 보이는 도형 5가지만 위에서 부터 1x1 정사각형으로 채울 수 있는 것을 알 수 있다.
  2.  반복문으로 board 를 돌며 해당 도형이 있는지를 찾는다.
  3.  해당 도형의 위로 가로막는 도형이 없는 지를 판단한다.
  4.  지울 수 있는 도형이라면 board에서 지워준다.

 

우선 가로로 3칸인지 세로로 3칸인지 두가지로 나누어서 도형을 판단하였다.

int checkShape(int r, int c){
    int num = copy_board[r][c];

    if(r - 2 >= 0 && copy_board[r-1][c] == num && copy_board[r-2][c] == num){
        return COLUMN;            
    }

    if(c - 2 >= 0 && copy_board[r][c-1] == num && copy_board[r][c-2] == num){
        return ROW;
    }

    return -1;
}

 

가로 3칸의 모양의 경우는 세가지다 

코드에서 위 그림의 순서대로 판단을 하였다.

boolean isRowPossible(int r, int c){

    if(r - 1 < 0){
        return false;
    }

    int num = copy_board[r][c];
    if(copy_board[r-1][c] == num){
        for(int i = r - 1 ; i >= 0 ; i--){
            if(copy_board[i][c-1] != 0 || copy_board[i][c-2] != 0){
                return false;
            }
        }

        copy_board[r-1][c] = 0;
        cleanRow(r, c);
        return true;
    }

    if(copy_board[r-1][c-1] == num){
        for(int i = r - 1 ; i >= 0 ; i--){
            if(copy_board[i][c] != 0 || copy_board[i][c-2] != 0){
                return false;
            }
        }

        copy_board[r-1][c-1] = 0;
        cleanRow(r, c);
        return true;
    }

    if(copy_board[r-1][c-2] == num){
        for(int i = r - 1 ; i >= 0 ; i--){
            if(copy_board[i][c] != 0 || copy_board[i][c-1] != 0){
                return false;
            }
        }

        copy_board[r-1][c-2] = 0;
        cleanRow(r, c);
        return true;
    }

    return false;
}

 

해당 도형의 위로 아무것도 가리는 것이 없다면 도형을 모두 0으로 바꿔주었다.

 

세로로 3칸의 경우는 2가지 도형이 존재한다.

코드에서 순서대로 판단하였다.

boolean isColPossible(int r, int c){

    int num = copy_board[r][c];

    if(c - 1 >= 0 && copy_board[r][c-1] == num){
        for(int i = r - 1 ; i >= 0 ; i--){
            if(copy_board[i][c - 1] != 0){
                return false;
            }
        }

        copy_board[r][c-1] = 0;
        cleanCol(r, c);
        return true;
    }

    if(c + 1 < copy_board.length && copy_board[r][c+1] == num){

        for(int i = r - 1 ; i >= 0 ; i--){
            if(copy_board[i][c + 1] != 0){
                return false;
            }
        }

        copy_board[r][c+1] = 0;
        cleanCol(r, c);
        return true;
    }

     return false;
}

 

이렇게 판단했을 때 위로 가리는 것이 없다면 도형을 모두 0으로 바꿔주었다.

 

 

<전체코드>

class Solution {
    
    int[][] copy_board;
    int ROW = 1, COLUMN = 2;
    public int solution(int[][] board) {
        int answer = 0;
        copy_board = new int[board.length][board.length];
        for(int i = 0 ; i < board.length ; i++){
            copy_board[i] = board[i].clone();
        }
        
        for(int i = 0 ; i < board.length ; i++){
            for(int j = 0 ; j < board.length ; j++){
                if(copy_board[i][j] != 0){
                    int dir = checkShape(i, j);
                    int num = board[i][j];
                    
                    if(dir == ROW && isRowPossible(i, j)){
                        answer++;
                    }
                    
                    if(dir == COLUMN && isColPossible(i, j)){
                        answer++;
                    } 
                    
                }
            }
        }
        
        return answer;
    }
        
    int checkShape(int r, int c){
        int num = copy_board[r][c];

        if(r - 2 >= 0 && copy_board[r-1][c] == num && copy_board[r-2][c] == num){
            return COLUMN;            
        }

        if(c - 2 >= 0 && copy_board[r][c-1] == num && copy_board[r][c-2] == num){
            return ROW;
        }

        return -1;
    }
    
    boolean isColPossible(int r, int c){

        int num = copy_board[r][c];

        if(c - 1 >= 0 && copy_board[r][c-1] == num){
            for(int i = r - 1 ; i >= 0 ; i--){
                if(copy_board[i][c - 1] != 0){
                    return false;
                }
            }

            copy_board[r][c-1] = 0;
            cleanCol(r, c);
            return true;
        }

        if(c + 1 < copy_board.length && copy_board[r][c+1] == num){

            for(int i = r - 1 ; i >= 0 ; i--){
                if(copy_board[i][c + 1] != 0){
                    return false;
                }
            }

            copy_board[r][c+1] = 0;
            cleanCol(r, c);
            return true;
        }

         return false;
    }   
    
    boolean isRowPossible(int r, int c){

        if(r - 1 < 0){
            return false;
        }

        int num = copy_board[r][c];
        if(copy_board[r-1][c] == num){
            for(int i = r - 1 ; i >= 0 ; i--){
                if(copy_board[i][c-1] != 0 || copy_board[i][c-2] != 0){
                    return false;
                }
            }

            copy_board[r-1][c] = 0;
            cleanRow(r, c);
            return true;
        }

        if(copy_board[r-1][c-1] == num){
            for(int i = r - 1 ; i >= 0 ; i--){
                if(copy_board[i][c] != 0 || copy_board[i][c-2] != 0){
                    return false;
                }
            }

            copy_board[r-1][c-1] = 0;
            cleanRow(r, c);
            return true;
        }

        if(copy_board[r-1][c-2] == num){
            for(int i = r - 1 ; i >= 0 ; i--){
                if(copy_board[i][c] != 0 || copy_board[i][c-1] != 0){
                    return false;
                }
            }

            copy_board[r-1][c-2] = 0;
            cleanRow(r, c);
            return true;
        }

        return false;
    }
    
    void cleanCol(int r, int c){
        
        for(int i = r ; i >= r - 2 ; i--){
            copy_board[i][c] = 0;
        }
        
        return;
    }
    
    void cleanRow(int r, int c){
        
        for(int i = c; i >= c - 2; i--){
            copy_board[r][i] = 0;
        }
        
        return;
    }
}

'알고리즘 공부 > 구현 , 시뮬레이션' 카테고리의 다른 글

[백준] 13335 트럭  (0) 2021.08.08
[백준] 16918 봄버맨  (0) 2021.08.02
[프로그래머스] 하노이의 탑  (0) 2021.06.23
[프로그래머스] 최고의 집합  (0) 2021.06.22
[프로그래머스] 줄 서는 방법  (0) 2021.06.22

'알고리즘 공부/구현 , 시뮬레이션'의 다른글

  • 현재글[프로그래머스] 블록게임

관련글

댓글

티스토리툴바