백준 g2 20061 모노미노도미노 2 c++

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

20061번: 모노미노도미노 2

 

문제 설명

• 빨강, 파랑, 초록으로 나뉘어진 특수한 보드가 있다.
• 빨간색 보드에 1*1, 2*1, 1*2인 블록을 놓을 수 있으며, 이는 파랑, 초록 보드에도 같이 놓여진다.
  • 파랑, 초록에 놓여질 때는 슬라이딩 하듯이 놓을 수 있는 가장 끝에 놓아진다.
• 한 행/열에 4칸이 모두 차면, 그 줄은 사라지고 점수를 1점 얻는다.
  • 해당 줄이 사라지면 그 위에 줄이 그대로 내려온다.
• 파랑, 초록 보드의 맨 위에는 연한 색 구간이 있는데, 여기에 블록이 있으면 블록이 존재하는 행/열 만큼 블록을 아래로 내린다. 내린 만큼 맨 밑 줄은 삭제된다.
• 블록을 놓는 횟수 N과 놓을 블록의 형태 t x y가 주어질 때, 얻을 수 있는 점수, 파랑 초록 보드에 블록이 놓여있는 칸 수를 출력한다. 

문제 풀이

1. 보드 구성

2. 빨강 보드에 블럭 놓기 -> 파랑, 초록에도 놓여짐

3. 행/열에 4칸이 다 차면 그 줄 삭제, 밑으로 삭제된 만큼 땡기기

4. 연한 색에 블록 있으면 그만큼 내리고, 내린만큼 밑 삭제

 

1. 보드 구성

3번 경우는 배열을 직접 내리고, 4번 경우는 cursor를 두어 cursor만 움직이려고 한다.

 

빨간 보드에 블록을 놓으면, 초록 보드는 블록의 y좌표만 필요하다. x좌표는 어차피 가능한만큼 맨 밑으로 땡길 거기 때문이다. 파랑 보드도 같은 이유로 블록의 x좌표만 필요하다.

 

초록 보드의 필요한 행 개수는 최대 블록을 10000번 놓을 수 있으므로, 2번 블록을 10000 놓는 다고 가정하면 20000개까지 필요하다.

Green[25000][4], Blue[4][25000]으로 둔다.

 

2. 빨강 보드에 블럭 놓기

putG(t, x, y)

빨강 보드에 t x y인 블록을 놓았을 때, Green 보드에 놓아주는 함수

 

먼저 x좌표 = i가 내려갈 수 있을 때까지 내려가야 하므로, i = gCur+5(초록 보드의 맨 위)부터 시작해서 gCur -1까지 내린다. gCur이 아닌 gCur-1까지 내려가는 이유는, 가다가 불가능한 경우를 만나면 break할 텐데 i == 0까지 내려가면, i==0에 놓을 수 있음에도 불구하고 i ==1에 블록을 놓게 된다.

 

그렇게 내린 i에 블록 모양에 맞게 블록을 놓는다.

int i = gCur + 5;
    while (i != gCur - 1) {
        if (t == 1) {
            if (Green[i][y] != 0)
                break;
        } else if (t == 2) {
            if (Green[i][y] != 0 || Green[i][y + 1] != 0) {
                break;
            }
        } else if (t == 3) {
            if (Green[i][y] != 0 || Green[i + 1][y] != 0) {
                break;
            }
        }
        i--;
    }

    i++;
    if (t == 1) {
        Green[i][y] = 1;
    } else if (t == 2) {
        Green[i][y] = 2;
        Green[i][y + 1] = 2;
    } else if (t == 3) {
        Green[i + 1][y] = 3;
        Green[i][y] = 3;
    }

 

 

3. 행/열에 4칸이 다 차면 그 줄 삭제, 밑으로 삭제된 만큼 땡기기

 

블록을 쌓은 i, i+1행 밖에 없으므로 그 줄에서만 4칸이 다 찼는지 검사하면 된다.

한 줄이 한 번에 움직이지 중력에 따라 각각의 칸이 따로 움직이는 게 아니기 때문에 연쇄 작용은 고려하지 않아도 된다.

 

i행과 i+1행을 따로 검사하는 이유는 2줄을 없애야 할 경우 문제가 되기 때문이다.

i행을 검사하고 한 줄을 내리게 되면, 검사해야했을 i+1행은 i행으로 내려가기 때문에 검사되지 않고, 기존의 i+2행이 i+1행으로 내려가 검사를 받게 된다. 

    bool flag = true;
    // 2. i, i+1행 검사
    // 2-1. i행 검사
    for (int j = 0; j < 4; j++) {
        if (Green[i][j] == 0) {
            flag = false;
            break;
        }
    }

    // 2-2. i+1행 검사
    bool flag2 = true;
    for (int j = 0; j < 4; j++) {
        if (Green[i + 1][j] == 0) {
            flag2 = false;
            break;
        }
    }

 

 

따라서 먼저 i번째 행을 삭제하고, 그 후에 i번째 행을 삭제했다면 i+1행이 아니라 i행(기존의 i+1행)을 검사하도록 하고, 그게 아니면 원래대로 i+1행을 검사하도록 한다.

if (flag) {
        for (int r = i; r < gCur + 6; r++) {
            for (int j = 0; j < 4; j++) {
                Green[r][j] = Green[r + 1][j];
            }
        }
        score++;
    }

    if (flag2) {
        int r = i + 1;
        if (flag) r = i;
        for (r; r < gCur + 6; r++) {
            for (int j = 0; j < 4; j++) {
                Green[r][j] = Green[r + 1][j];
            }
        }
        score++;
    }

 

4. 연한 색에 블록 있으면 그만큼 내리고, 내린만큼 밑 삭제

 

이는 만약 연한 색 구간에 블록이 있으면, 그 줄만큼 cursor를 더해주면 된다. 

// 1. gCur
int cnt = 0;
for (int i = gCur + 4; i < gCur + 6; i++) {
    for (int j = 0; j < 4; j++) {
        if (Green[i][j] != 0) {
            cnt++;
            break;
        }
    }
}

gCur += cnt;

 

 

전체 코드

/*boj g2 20061 모노미노도미노 2*/
#include <iostream>
#define MAXN 25000
using namespace std;

int T;
int Green[MAXN][4];
int Blue[4][MAXN];

int gCur = 0; // Green board의 cur ~ cur + 3가 유효 범위, cur + 4~5 는 연한색
int bCur = 0;

int score = 0;

void putG(int t, int x, int y) { // t x y인 블럭을 Green에 놓는 함수
    // y는 그대로, x는 맨 밑으로 내려가야 함
    // 불가능할 때까지 내려가기
    int i = gCur + 5;
    while (i != gCur - 1) {
        if (t == 1) {
            if (Green[i][y] != 0)
                break;
        } else if (t == 2) {
            if (Green[i][y] != 0 || Green[i][y + 1] != 0) {
                break;
            }
        } else if (t == 3) {
            if (Green[i][y] != 0 || Green[i + 1][y] != 0) {
                break;
            }
        }
        i--;
    }

    i++;
    if (t == 1) {
        Green[i][y] = 1;
    } else if (t == 2) {
        Green[i][y] = 2;
        Green[i][y + 1] = 2;
    } else if (t == 3) {
        Green[i + 1][y] = 3;
        Green[i][y] = 3;
    }

    bool flag = true;
    // 2. i, i+1행 검사
    // 2-1. i행 검사
    for (int j = 0; j < 4; j++) {
        if (Green[i][j] == 0) {
            flag = false;
            break;
        }
    }

    // 2-2. i+1행 검사
    bool flag2 = true;
    for (int j = 0; j < 4; j++) {
        if (Green[i + 1][j] == 0) {
            flag2 = false;
            break;
        }
    }
    if (flag) {
        for (int r = i; r < gCur + 6; r++) {
            for (int j = 0; j < 4; j++) {
                Green[r][j] = Green[r + 1][j];
            }
        }
        score++;
    }

    if (flag2) {
        int r = i + 1;
        if (flag) r = i;
        for (r; r < gCur + 6; r++) {
            for (int j = 0; j < 4; j++) {
                Green[r][j] = Green[r + 1][j];
            }
        }
        score++;
    }
}

void putB(int t, int x, int y) { // t x y인 블럭을 Green에 놓는 함수
    // x는 그대로, y는 맨 밑으로 내려가야 함
    // 불가능할 때까지 내려가기
    int j = bCur + 5;
    while (j != bCur - 1) {
        if (t == 1) {
            if (Blue[x][j] != 0)
                break;
        } else if (t == 2) {
            if (Blue[x][j] != 0 || Blue[x][j + 1] != 0) {
                break;
            }
        } else if (t == 3) {
            if (Blue[x][j] != 0 || Blue[x + 1][j] != 0) {
                break;
            }
        }
        j--;
    }

    j++;
    if (t == 1) {
        Blue[x][j] = 1;
    } else if (t == 2) {
        Blue[x][j] = 2;
        Blue[x][j + 1] = 2;
    } else if (t == 3) {
        Blue[x + 1][j] = 3;
        Blue[x][j] = 3;
    }

    bool flag = true;
    // 2. j, j+1행 검사
    // 2-1. j행 검사
    for (int i = 0; i < 4; i++) {
        if (Blue[i][j] == 0) {
            flag = false;
            break;
        }
    }

    // 2-2. j+1행 검사
    bool flag2 = true;
    for (int i = 0; i < 4; i++) {
        if (Blue[i][j + 1] == 0) {
            flag2 = false;
            break;
        }
    }

    if (flag) {
        for (int c = j; c < bCur + 6; c++) {
            for (int i = 0; i < 4; i++) {
                Blue[i][c] = Blue[i][c + 1];
            }
        }
        score++;
    }

    if (flag2) {
        int c = j + 1;
        if (flag) c = j;
        for (c; c < bCur + 6; c++) {
            for (int i = 0; i < 4; i++) {
                Blue[i][c] = Blue[i][c + 1];
            }
        }
        score++;
    }
}

void lightSpace() {
    // 1. gCur
    int cnt = 0;
    for (int i = gCur + 4; i < gCur + 6; i++) {
        for (int j = 0; j < 4; j++) {
            if (Green[i][j] != 0) {
                cnt++;
                break;
            }
        }
    }

    gCur += cnt;

    // 2. bCur
    cnt = 0;
    for (int j = bCur + 4; j < bCur + 6; j++) {
        for (int i = 0; i < 4; i++) {
            if (Blue[i][j] != 0) {
                cnt++;
                break;
            }
        }
    }
    bCur += cnt;
}

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

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

void output() {
    cout << score << "\n";

    int bCnt = 0;
    for (int i = 0; i < 4; i++) {
        for (int j = bCur; j < bCur + 6; j++) {
            if (Blue[i][j] != 0)
                bCnt++;
        }
    }
    int gCnt = 0;
    for (int i = gCur; i < gCur + 6; i++) {
        for (int j = 0; j < 4; j++) {
            if (Green[i][j] != 0)
                gCnt++;
        }
    }
    cout << bCnt + gCnt << "\n";
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    int t, x, y;
    while (T--) {
        cin >> t >> x >> y;

        // 1. G, B 보드에 넣기 2. 쌓인 행/열 삭제하고 밑으로 내리기
        putG(t, x, y);
        putB(t, x, y);
        // 3. 연한 색 칸에 뭐 있으면 그만큼 내리기
        lightSpace();
        // printGreen();
        // printBlue();
    }
    output();
}