[Lv5] 블록 게임

https://programmers.co.kr/learn/challenges

프로그래밍 강의 | 프로그래머스

문제 설명

블록게임

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

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

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

게임규칙

아래 그림과 같이 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*1 블록을 채워서 한 도형이 없어지는 것이지, 가로줄이 없어지는 것도 아니고,

받쳐주던 블록이 없어진다고 블록들이 내려앉는 것도 아닙니다.

 

블록은 같은 숫자의 4칸으로 이루어진 도형입니다.

숫자 정보를 이용해서 블록이 어떻게 생긴지 알아야 합니다.

우선, 아래의 1,2,5,8,10,11,12번째 모델은 빈 틈을 자기자신이 위에서 가리고 있기 때문에,

주변환경과 상관없이 항상 삭제가 불가능한 모델임을 기억해둡니다.

□□□

□□□

□□□

이 3*3을 생각해봅니다. 저 12가지 도형은 모두 3*3에 들어올 수 있습니다.

 

①②③　①②□　①□□　□①□

□□④　③□□　②③④　□②□

□□□　④□□　□□□　③④□

 

①②③　①□□　□□①　①②□

④□□　②□□　②③④　□③□

□□□　③④□　□□□　□④□

 

□①□　①□□　①②③　□①□

②③④　②③□　□④□　②③□

□□□　④□□　□□□　□④□

왼쪽위에서 오른쪽아래로 내려오면서 같은 고유숫자를 만났을 때의 순서로 ①~④으로 순서를 매길 수 있습니다.

이 순서로 도형을 알 수 있는데,

①과 ②의 높이가 같으면 1,2,5,8,11. 다르면 3,4,6,7,9,10,12.

①과 ③의 높이가 같으면 1,5,11, 다르면 2,3,4,6,7,8,9,10,12.

와 같이 1~12개의 도형 생김새를 유추할 수 있습니다.

public int getModel(int cal1, int cal2, int cal3, int cal4, int cal5) {
    if(cal1==0) {	// 1,5,11
        if(cal4==2) {	// 1
            return 1;
        } else if(cal4==0) {	// 5
            return 5;
        } else if(cal4==1) {	// 11
            return 11;
        }
    } else if(cal1==1) {	// 2,3,7,8,9,10,12
        if(cal2==0) {	// 2,9,12
            if(cal3==2) {	// 2,12
                if(cal5==0) {	// 2
                    return 2;
                } else if(cal5==1) {	// 12
                    return 12;
                }
            } else if(cal3==1) {	// 9
                return 9;
            }
        } else if(cal2==1) {	// 3,8,10
            if(cal3==1) {	// 3
                return 3;
            } else if(cal3==2) {	// 8,10
                if(cal4==1) {	// 8
                    return 8;
                } else if(cal4==0) {	// 10
                    return 10;
                }
            }
        } else if(cal2==-1) {	// 7
            return 7;
        }
    } else if(cal1==2) {	// 4,6
        if(cal2==-1) {	// 4
            return 4;
        } else if(cal2==0) {	// 6
            return 6;
        }
    }
    return 0;
}

※ cal1=③의y-①의y / cal2=③의x-①의x / cal3=④의y-①의y / cal4=④의x-①의x / cal5=②의y-①의y

 

 

int answer = 0;
int sel = -1;
int[][] now = new int[][] {{-1,-1},{-1,-1},{-1,-1},{-1,-1}};
int model = 0;
HashSet<Integer> disable = new HashSet<>();
HashSet<Integer> never = new HashSet<>();

선택한 블록을 이루고 있는 고유 번호가 저장될 sel,

4가지 블록의 y,x를 차례로 기록할 now[][],

선택한 블록이 어느 모델인지 기록할 model,

 

그리고 해당 블록이 전혀 없어질 수 없는(1,2,5,8,10,11,12) 도형이라면 never에,

해당 블록이 우선 현재로는 없어질 수 없는 상태라면 disable에 기록할겁니다.

 

 

while(true) {
    for(int i=0;i<board.length;i++) {
        for(int j=0;j<board.length;j++) {
            if(board[i][j]!=0 && !disable.contains(board[i][j]) && !never.contains(board[i][j])) {
                if(sel==-1) {
                    sel=board[i][j];
                    now[0][0] = i;
                    now[0][1] = j;
                } else if(sel==board[i][j]) {
                    for(int k=0;k<now.length;k++) {
                        if(now[k][0]==-1) {
                            now[k][0] = i;
                            now[k][1] = j;
                            break;
                        }
                    }
                }
            }
            if(now[3][0]!=-1) break;
        }
        if(now[3][0]!=-1) break;
    }
    if(sel==-1) break;
    int cal1 = now[2][0] - now[0][0];
    int cal2 = now[2][1] - now[0][1];
    int cal3 = now[3][0] - now[0][0];
    int cal4 = now[3][1] - now[0][1];
    int cal5 = now[1][0] - now[0][0];
    model = getModel(cal1, cal2, cal3, cal4, cal5);
    if(model==1||model==2||model==5||model==8||model==10||model==11||model==12) {
        never.add(sel);
        now = new int[][] {{-1,-1},{-1,-1},{-1,-1},{-1,-1}};
        sel = -1;
        model = 0;
    } else {
        int y1 = -1;
        int x1 = -1;
        int y2 = -1;
        int x2 = -1;
        if(model==3) {
            y1 = now[0][0];
            x1 = now[2][1];
            y2 = now[0][0];
            x2 = now[3][1];
        } else if(model==4) {
            y1 = now[0][0];
            x1 = now[2][1];
            y2 = now[1][0];
            x2 = now[2][1];
        } else if(model==6) {
            y1 = now[0][0];
            x1 = now[3][1];
            y2 = now[1][0];
            x2 = now[3][1];
        } else if(model==7) {
            y1 = now[0][0];
            x1 = now[1][1];
            y2 = now[0][0];
            x2 = now[2][1];
        } else if(model==9) {
            y1 = now[0][0];
            x1 = now[1][1];
            y2 = now[0][0];
            x2 = now[3][1];
        }
        boolean isAllZero = true;
        for(int i=0;i<=y1;i++) {
            if(board[i][x1]!=0) isAllZero = false;
        }
        for(int i=0;i<=y2;i++) {
            if(board[i][x2]!=0) isAllZero = false;
        }
        if(isAllZero) {
            answer++;
            board[now[0][0]][now[0][1]] = 0;
            board[now[1][0]][now[1][1]] = 0;
            board[now[2][0]][now[2][1]] = 0;
            board[now[3][0]][now[3][1]] = 0;
            now = new int[][] {{-1,-1},{-1,-1},{-1,-1},{-1,-1}};
            sel = -1;
            model = 0;
            disable = new HashSet<>();
        } else {
            disable.add(sel);
            now = new int[][] {{-1,-1},{-1,-1},{-1,-1},{-1,-1}};
            sel = -1;
            model = 0;
        }
    }
}
return answer;

이후 전체코드는 이렇게 진행됩니다.

다시 아래에서 부분적으로 나눠봅니다.

 

 

    for(int i=0;i<board.length;i++) {
        for(int j=0;j<board.length;j++) {
            if(board[i][j]!=0 && !disable.contains(board[i][j]) && !never.contains(board[i][j])) {
                if(sel==-1) {
                    sel=board[i][j];
                    now[0][0] = i;
                    now[0][1] = j;
                } else if(sel==board[i][j]) {
                    for(int k=0;k<now.length;k++) {
                        if(now[k][0]==-1) {
                            now[k][0] = i;
                            now[k][1] = j;
                            break;
                        }
                    }
                }
            }
            if(now[3][0]!=-1) break;
        }
        if(now[3][0]!=-1) break;
    }
    if(sel==-1) break;

while문 첫부분입니다. board의 왼쪽위에서 아래로 내려오면서 0이 아닌 블록을 찾습니다.

만약 이 블록이 never에도 없고(never는 고려대상이 아님.), disable에도 없다면(disable도 현재는 삭제불가능.)

 

sel에 이 고유번호를 기록하면서 첫번째 블록의 y,x값 저장.

sel과 같은 번호를 만날 때까지 2,3,4번째 블록의 y,x를 저장합니다.

4번째 블록까지 저장이 마치면 위의 탐색부분은 빠져나오게 break합니다.

 

만약 모든 board를 탐색했는데도 sel이 -1이라는건 모두 삭제불가거나 블록이 없다는 것이므로 while문 자체를 종료합니다.

 

 

    int cal1 = now[2][0] - now[0][0];
    int cal2 = now[2][1] - now[0][1];
    int cal3 = now[3][0] - now[0][0];
    int cal4 = now[3][1] - now[0][1];
    int cal5 = now[1][0] - now[0][0];
    model = getModel(cal1, cal2, cal3, cal4, cal5);

※ cal1=③의y-①의y / cal2=③의x-①의x / cal3=④의y-①의y / cal4=④의x-①의x / cal5=②의y-①의y

위에서 나왔던 함수로 model의 번호를 1~12로 구합니다.

 

 

 

    if(model==1||model==2||model==5||model==8||model==10||model==11||model==12) {
        never.add(sel);
        now = new int[][] {{-1,-1},{-1,-1},{-1,-1},{-1,-1}};
        sel = -1;
        model = 0;
    } else {
        int y1 = -1;
        int x1 = -1;
        int y2 = -1;
        int x2 = -1;
        if(model==3) {
            y1 = now[0][0];
            x1 = now[2][1];
            y2 = now[0][0];
            x2 = now[3][1];
        } else if(model==4) {
            y1 = now[0][0];
            x1 = now[2][1];
            y2 = now[1][0];
            x2 = now[2][1];
        } else if(model==6) {
            y1 = now[0][0];
            x1 = now[3][1];
            y2 = now[1][0];
            x2 = now[3][1];
        } else if(model==7) {
            y1 = now[0][0];
            x1 = now[1][1];
            y2 = now[0][0];
            x2 = now[2][1];
        } else if(model==9) {
            y1 = now[0][0];
            x1 = now[1][1];
            y2 = now[0][0];
            x2 = now[3][1];
        }
        boolean isAllZero = true;
        for(int i=0;i<=y1;i++) {
            if(board[i][x1]!=0) isAllZero = false;
        }
        for(int i=0;i<=y2;i++) {
            if(board[i][x2]!=0) isAllZero = false;
        }
        if(isAllZero) {
            answer++;
            board[now[0][0]][now[0][1]] = 0;
            board[now[1][0]][now[1][1]] = 0;
            board[now[2][0]][now[2][1]] = 0;
            board[now[3][0]][now[3][1]] = 0;
            now = new int[][] {{-1,-1},{-1,-1},{-1,-1},{-1,-1}};
            sel = -1;
            model = 0;
            disable = new HashSet<>();
        } else {
            disable.add(sel);
            now = new int[][] {{-1,-1},{-1,-1},{-1,-1},{-1,-1}};
            sel = -1;
            model = 0;
        }
    }

만약 모델이 1,2,5,8,10,11,12라면 아예 삭제 불가능한 모델이니

바로 never에 고유번호를 추가하고 값들을 초기로 돌려주고 다시 while문으로 돌아가서 탐색을 합니다.

(never에 저장되어있으니 이 고유번호는 패스될겁니다.)

 

각 모델의 빈 두 칸에 해당할 y,x를 기록합니다.

실제로 board에서 저 두 칸의 x값은 고정한 채 맨 위에서부터 가리고 있는 블록이 하나도 없는지 조사합니다.

 

둘 다 가리고 있는게 없으면 삭제가 가능하니,

4블록을 0으로 없애고,(answer는 ++) 값들을 초기로 돌려줍니다.

또한 이 블록이 없어지면서 기존에 현재불가능 판정이었던 애들이 다시 가능해질 수 있으므로 disable을 비워줍니다.

 

둘 중 하나라도 뭔가 가리고 있으면 삭제가 불가능하니,

disable에 기록하고 값들을 초기로 돌려줍니다.

 

 

while문을 돌면서 더 이상 삭제할 수 없이 다 돌고나면 답을 반환하게 됩니다.

 

블록을 제거하면서 disable을 구분없이 모두 비워버리는게 찝찝하지만 이 상태로도 시간초과는 없습니다.