[백준 20061][C++] 모노미노도미노 2

문제

https://www.acmicpc.net/problem/20061

20061번: 모노미노도미노 2

 

풀이 과정

1. 각 블록의 입력에 따라 초록색 보드와 파란색 보드에 새로운 블록을 추가한다. (대칭 관계 이용)

2. 블록이 추가된 상황에서 초록색 보드와 파란색 보드를 업데이트하는 함수

    2-1. 보드의 한 Row(4칸)이 1로 가득 찬 경우 테트리스처럼 점수를 얻고 해당 줄을 삭제

    2-2. 업데이트 직전 보드의 블록이 0, 1번 Row에 존재하면 밀어내어 0, 1번 Row를 비운다.

3. 업데이트하며 추가했던 score 값과 최종적으로 보드에 존재하는 칸의 수를 출력한다.

 

세부 풀이

 

(1) push_block 함수 (초록색 보드를 기준으로 작성) / update_block 함수

해당 함수를 구현할 때, 문제의 각 보드의 index에 주목했다.

<그림 1> 모노미노도미노 게임 보드

초록색 보드의 인덱스는 배열[6][4]의 형태와 같았다. 하지만 파란색 보드의 경우 배열[4][6]의 형태로 초록색 보드의 각 좌표 대칭 형태의 모양이다. 주어지는 입력을 각 보드에 맞게 조정해 준다면 동일한 함수를 구현하여 초록색 보드와 파란색 보드에 블록을 추가하고 업데이트할 수 있을 것이라고 생각했다. 주어지는 블록의 입력 케이스도 단순한 3가지 경우였다. 따라서 초록색 보드의 형태에 맞게 push_block 함수를 구현한 뒤, 입력을 조절하여 처리하는 update_block 함수를 만들었다.

 

t=2(좌측)일 때와 t=3(우측)일 때의 이미지

 

t=1 일 때, 1칸의 블록이 들어오는 경우에는 블록의 모양의 변경 없이 x, y 좌표만 바꾸어 입력한다. (Line 66 - Line 69)

2칸이 들어오게 된다면 t=2 모양은 t=3 모양으로, t=3 모양은 t=2 모양으로 바꾸어 파란색 보드를 업데이트한다. 

t=3 일 때 파란색 보드의 모양과, t=2 일 때의 초록색 보드의 모양이 같은 것을 확인할 수 있다.

이런 대칭성을 바탕으로 push_block이라는 하나의 함수를 작성했다. (초록색 보드 기준)

 

시작점의 기준 index를 모두 1로 설정하였다. 블록을 추가한 뒤 무조건 0,1 Row는 비어있기 때문에 index를 1부터 시작하여 index+1 위치를 확인하며 진행하면 된다. 만약 새로운 위치의 값이 1 이거나 범위를 벗어난다면 반복문을 멈추고 해당 위치에 타입에 맞게 블록을 입력하면 된다. 이때 t=3 같은 경우는 가로방향이므로 v [index+1][y]와 v [index+1][y+1]을 같이 확인하며 반복문을 진행해야 한다.

 

(2-1) update_line의 꽉 찬 라인 지우기

이중 배열을 통해 한 번의 탐색을 통해 기존의 초록색 보드나, 파란색 보드의 상태 중 삭제되지 않는 부분만을 vector를 통해 저장한 뒤, 지워진 만큼 0으로 구성된 Row를 추가한 뒤 vector에 저장되어 있는 정보들을 보드에 이어서 저장했다.

 

 

(2-2) update_line의 라인 밀어 내기

꽉 찬 라인을 지운 뒤에도 Row 0,1에 블록이 남아 있다면 마지막 Row부터 밀어내며 Row 0, 1을 비우는 과정이다. 두 Row를 탐색하며 블록이 존재하면 line_push_cnt 변수를 증가시킨 뒤 break 하여 두 Row에 대해서 탐색을 진행했다. ( 0 <=line_push_cnt <= 2 )

 

(3)

N번의 반복을 진행한 뒤, update_line을 통해 증가된 score의 값과 최종 보드의 형태에 존재하는 블록의 칸 수를 출력한다.

 

 

소스 코드

#include <iostream>
#include <vector>

using namespace std;

int green[6][4];
int blue[6][4];
int N, score;

struct txy{
    int t,x,y;
};

vector<txy> txy_v;

void print_map(int v[6][4]){
    for(int i=0; i<6; i++){
        for(int j=0;j<4;j++){
            cout << v[i][j] << " ";
        }
        cout << "\n";
    }
    cout <<"\n";
}


void Input(){
    cin >> N;
    txy one;
    for(int i=0;i<N;i++){
        cin >> one.t >> one.x >> one.y;
        txy_v.push_back(one);
    }
    
}

//초록색을 기준으로 작성
void push_block(int t, int x, int y, int v[6][4]){
    int newX=1;
    if(t==1){
        while(v[newX+1][y]!=1 && (newX+1<=5)){
            newX++;
        }
        v[newX][y]=1;
    }
    else if(t==2){
        while((v[newX+1][y]!=1 && v[newX+1][y+1]!=1) && (newX+1<=5)){
            newX++;
        }
        v[newX][y]=1;
        v[newX][y+1]=1;
    }

    else if(t==3){
        while((v[newX+1][y]!=1) && (newX+1<=5)){
            newX++;
        }
        v[newX][y]=1;
        v[newX-1][y]=1;
    }
}

void update_block(int t, int x, int y){
    if(t==1){
        push_block(t,x,y, green);
        push_block(t,y,x, blue);
    }
    if(t==2){
        push_block(t,x,y, green);
        push_block(3,y,x, blue);
    }
    if(t==3){
        push_block(t,x,y, green);
        push_block(2,y,x, blue);
    }
}

//꽉찬 라인 지우기 후, line 밀어내기 수행
void update_line(int v[6][4]){
    //꽉찬 라인 지우기
    vector< vector<int>> temp_vectors;
    int delete_cnt=0;
    int cnt;
    for(int i=0;i<=6;i++){
        cnt = 0;
        vector<int> temp;
        for(int j=0;j<4;j++){
            temp.push_back(v[i][j]);
            if(v[i][j]==1) cnt++;
        }
        if(cnt==4){
            delete_cnt++;
            score++;
            continue;
        }
        else{
            temp_vectors.push_back(temp);
        }
    }

    int idx=0;
    for(int i=0;i<6;i++){
        if(i<delete_cnt){
            for(int j=0;j<4;j++) v[i][j]=0;
        }
        else{
            for(int j=0;j<4;j++) v[i][j]=temp_vectors[idx][j];
            idx++;
        }
    }


    //라인 밀어내기
    int line_push_cnt=0;
    for(int i=0;i<2;i++){
        for(int j=0;j<4;j++){
            if(v[i][j]!=0) {
                line_push_cnt++;
                break;
            }
        }
    }

    while(line_push_cnt--){
        for(int i=4;i>=0;i--){
            for(int j=0;j<4;j++){
                v[i+1][j]=v[i][j];
            }
        }
        for(int j=0;j<4;j++){
            v[0][j]=0;
        }        
    }
}

void solve(){
    for(int i=0;i<N;i++){
        txy one = txy_v[i];
        update_block(one.t,one.x,one.y);
        update_line(green);
        update_line(blue);
    }

    int total_tiles=0;
    for(int i=0;i<6;i++){
        for(int j=0;j<4;j++){
            if(green[i][j]==1) total_tiles++;
            if(blue[i][j]==1) total_tiles++;
        }
    }

    cout << score << "\n" << total_tiles << "\n";
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    Input();
    solve();
    return 0;
}

 

결과 및 후기