백준 p5 19235 모노미노도미노 c++

 

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

19235번: 모노미노도미노

 

문제 설명

전반적인 내용은 모노미노도미노 2와 같다(https://kyj0032.tistory.com/40). 달라진 점은 행이 삭제될 때, 중력의 영향을 받아 블록들이 밑으로 내려온다는 것

1. 이때 2*1이나 1*2 크기의 블록들은 하나로 쳐서, 한 칸만 밑으로 내려오는 경우는 없다. 

2. 또한, 지워야 할 행이 2줄 이상일 때는 한 줄 지우고 떨어뜨리고 한 줄 지우고 떨어뜨리고 .. 가 아니라 한 번에 다 지우고 한 번에 떨어뜨려야 한다. 

왜냐하면 2줄이 지워져야 할 때, 한 줄 지우고 떨어뜨리면 배치된 블록 모양이 바뀌어 나머지 한 줄을 지울 수 없기 때문이다.

 

이 두 가지 점에 유의해서 코드를 짜면 된다.

 

1. 블록 한 번에 지우기

while (지워진 행이 있을 때까지 반복) {
    for (i: Green보드의 행)
        if  해당 행의 칸이 다 채워지면 {
            Green[i][j] = 0으로 초기화
            score++;
        }
    }
    if 지워진 행이 있으면
        // 삭제된 행 위에 있는 블록들을 아래로 내리기
        pushDownG(gCur);
    }
}

// 2. 행 검사
    bool again = true;
    while (again) {
        again = false;
        bool flag = false;
        for (int i = gCur; i < gCur + 6; i++) {
            if (Green[i][0] != 0 && Green[i][1] != 0 &&
                Green[i][2] != 0 && Green[i][3] != 0) {
                for (int j = 0; j < 4; j++) {
                    Green[i][j] = 0;
                }
                flag = true;
                score++;
            }
        }
        if (flag) { // 한 번 더 수행
            again = true;
            // 삭제된 행 위에 있는 블록들을 아래로 내리기
            pushDownG(gCur);
        }
    }

 

 

2. 중력에 의해 블록 떨어뜨리기

 

왜 임의로 type 4,5를 추가했냐면,

 

예를 들어

2 2 0 0

1 0 0 0

일 때, 첫 번째 2를 검사할 때 2 2는 붙어있기 때문에 1*2 블록으로 인식이 되어 내려가지 않는다.

두 번째 2를 검사할 때, j, j+1을 검사하기 때문에 1*1 블록으로 인식이 된다. 그래서 두 번째 2는 한 칸 내려가서 내 의도와는 다르게 한 칸씩 떨어지는 로직이 되어버린다.

 

2 0 0 0

1 2 0 0 

 

이를 방지하기 위해 type4를 추가해 현재 칸 왼쪽에도 같은 칸이 있는 경우, 하나의 블록으로 인식하도록 하여 떨어지지 않도록 해주었다. type5도 같은 이유

 

다만 이렇게 하면 

예를 들어, 

4 0 0 0

4 0 0 0

일 때, 위쪽의 4가 현재 칸이라고 생각해보자. 이때 밑에 있는 4를 인식해 하나의 블록으로 인식하는 것은 성공했다.

그러나 불가능할 때까지 내려가는 과정(di) 에서, 위쪽 4가 i=0 즉 맨 밑으로 내려가버리면, 

0 0 0 0

4 0 0 0

-------------- 

4 0 0 0

이 되어 밑 4가 가려진다. 

 

이를 방지하기 위해 불가능할 때까지 내려가는 과정에서, di -1 < gCur이면 역시 break한다는 명령문을 추가해주었다.

void pushDownG(int x) {
    for (int i = x; i < gCur + 6; i++) {
        for (int j = 0; j < 4; j++) {
            // 블럭 찾기
            if (Green[i][j] == 0) continue;

            int type = 1;
            int val = Green[i][j];
            if (Green[i][j + 1] == Green[i][j]) {
                type = 2;
                Green[i][j + 1] = 0;
            } else if (Green[i + 1][j] == Green[i][j]) {
                type = 3;
                Green[i + 1][j] = 0;
            } else if (j - 1 >= 0 && Green[i][j - 1] == Green[i][j]) {
                type = 4;
                Green[i][j - 1] = 0;
            } else if (i - 1 >= gCur && Green[i - 1][j] == Green[i][j]) {
                type = 5;
                Green[i - 1][j] = 0;
            }
            Green[i][j] = 0;

            // 불가능할 때까지 내려가기
            int di = i;
            while (di != gCur - 1) {
                if (type == 1) {
                    if (Green[di][j] != 0)
                        break;
                } else if (type == 2) {
                    if (Green[di][j] != 0 || Green[di][j + 1] != 0) {
                        break;
                    }
                } else if (type == 3) {
                    if (Green[di][j] != 0 || Green[di + 1][j] != 0) {
                        break;
                    }
                } else if (type == 4) {
                    if (j - 1 < 0 || Green[di][j] != 0 || Green[di][j - 1] != 0) {
                        break;
                    }
                } else if (type == 5) {
                    if (di - 1 < gCur || Green[di][j] != 0 || Green[di - 1][j] != 0) {
                        break;
                    }
                }
                di--;
            }

            di++;
            Green[di][j] = val;
            if (type == 1) {
                continue;
            } else if (type == 2) {
                Green[di][j + 1] = val;
            } else if (type == 3) {
                Green[di + 1][j] = val;
            } else if (type == 4) {
                Green[di][j - 1] = val;
            } else if (type == 5) {
                Green[di - 1][j] = val;
            }
        }
    }
}

 

 

전체 코드

/*boj p5 19235 모노미노도미노*/
#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 printGreen() {
    cout << "============\n";
    for (int i = gCur + 5; i >= gCur; 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 + 6; j >= bCur; j--) {
            cout << Blue[i][j] << " ";
        }
        cout << "\n";
    }
}
void pushDownG(int x) {
    for (int i = x; i < gCur + 6; i++) {
        for (int j = 0; j < 4; j++) {
            // 블럭 찾기
            if (Green[i][j] == 0) continue;

            int type = 1;
            int val = Green[i][j];
            if (Green[i][j + 1] == Green[i][j]) {
                type = 2;
                Green[i][j + 1] = 0;
            } else if (Green[i + 1][j] == Green[i][j]) {
                type = 3;
                Green[i + 1][j] = 0;
            } else if (j - 1 >= 0 && Green[i][j - 1] == Green[i][j]) {
                type = 4;
                Green[i][j - 1] = 0;
            } else if (i - 1 >= gCur && Green[i - 1][j] == Green[i][j]) {
                type = 5;
                Green[i - 1][j] = 0;
            }
            Green[i][j] = 0;

            // 불가능할 때까지 내려가기
            int di = i;
            while (di != gCur - 1) {
                if (type == 1) {
                    if (Green[di][j] != 0)
                        break;
                } else if (type == 2) {
                    if (Green[di][j] != 0 || Green[di][j + 1] != 0) {
                        break;
                    }
                } else if (type == 3) {
                    if (Green[di][j] != 0 || Green[di + 1][j] != 0) {
                        break;
                    }
                } else if (type == 4) {
                    if (j - 1 < 0 || Green[di][j] != 0 || Green[di][j - 1] != 0) {
                        break;
                    }
                } else if (type == 5) {
                    if (di - 1 < gCur || Green[di][j] != 0 || Green[di - 1][j] != 0) {
                        break;
                    }
                }
                di--;
            }

            di++;
            Green[di][j] = val;
            if (type == 1) {
                continue;
            } else if (type == 2) {
                Green[di][j + 1] = val;
            } else if (type == 3) {
                Green[di + 1][j] = val;
            } else if (type == 4) {
                Green[di][j - 1] = val;
            } else if (type == 5) {
                Green[di - 1][j] = val;
            }
        }
    }
}

void pushDownB(int y) {
    for (int j = y; j < bCur + 6; j++) {
        for (int i = 0; i < 4; i++) {
            // 블럭 찾기
            if (Blue[i][j] == 0) continue;

            int type = 1;
            int val = Blue[i][j];
            if (Blue[i][j + 1] == Blue[i][j]) {
                type = 2;
                Blue[i][j + 1] = 0;
            } else if (Blue[i + 1][j] == Blue[i][j]) {
                type = 3;
                Blue[i + 1][j] = 0;
            } else if (j - 1 >= bCur && Blue[i][j - 1] == Blue[i][j]) {
                type = 4;
                Blue[i][j - 1] = 0;
            } else if (i - 1 >= 0 && Blue[i - 1][j] == Blue[i][j]) {
                type = 5;
                Blue[i - 1][j] = 0;
            }
            Blue[i][j] = 0;

            int dj = j;
            // 불가능할 때까지 내려가기
            while (dj != bCur - 1) {
                if (type == 1) {
                    if (Blue[i][dj] != 0)
                        break;
                } else if (type == 2) {
                    if (Blue[i][dj] != 0 || Blue[i][dj + 1] != 0) {
                        break;
                    }
                } else if (type == 3) {
                    if (Blue[i][dj] != 0 || Blue[i + 1][dj] != 0) {
                        break;
                    }
                } else if (type == 4) {
                    if (dj - 1 < bCur || Blue[i][dj] != 0 || Blue[i][dj - 1] != 0) {
                        break;
                    }
                } else if (type == 5) {
                    if (i - 1 < 0 || Blue[i][dj] != 0 || Blue[i - 1][dj] != 0) {
                        break;
                    }
                }
                dj--;
            }

            dj++;
            Blue[i][dj] = val;
            if (type == 1) {
                continue;
            } else if (type == 2) {
                Blue[i][dj + 1] = val;
            } else if (type == 3) {
                Blue[i + 1][dj] = val;
            } else if (type == 4) {
                Blue[i][dj - 1] = val;
            } else if (type == 5) {
                Blue[i - 1][dj] = val;
            }
        }
    }
}

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] = T + 1;
    } else if (t == 2) {
        Green[i][y] = T + 1;
        Green[i][y + 1] = T + 1;
    } else if (t == 3) {
        Green[i + 1][y] = T + 1;
        Green[i][y] = T + 1;
    }

    // 2. 행 검사
    bool again = true;
    while (again) {
        again = false;
        bool flag = false;
        for (int i = gCur; i < gCur + 6; i++) {
            if (Green[i][0] != 0 && Green[i][1] != 0 &&
                Green[i][2] != 0 && Green[i][3] != 0) {
                for (int j = 0; j < 4; j++) {
                    Green[i][j] = 0;
                }
                flag = true;
                score++;
            }
        }
        if (flag) { // 한 번 더 수행
            again = true;
            // 삭제된 행 위에 있는 블록들을 아래로 내리기
            pushDownG(gCur);
        }
    }
}

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] = T + 1;
    } else if (t == 2) {
        Blue[x][j] = T + 1;
        Blue[x][j + 1] = T + 1;
    } else if (t == 3) {
        Blue[x + 1][j] = T + 1;
        Blue[x][j] = T + 1;
    }

    // 2. 행 검사
    bool again = true;
    while (again) {
        again = false;
        bool flag = false;
        for (int j = bCur; j < bCur + 6; j++) {
            if (Blue[0][j] != 0 && Blue[1][j] != 0 &&
                Blue[2][j] != 0 && Blue[3][j] != 0) {
                for (int i = 0; i < 4; i++) {
                    Blue[i][j] = 0;
                }
                flag = true;
                score++;
            }
        }
        if (flag) { // 해당 행 삭제, 한 번 더 수행
            again = true;
            // 삭제된 행 위에 있는 블록들을 아래로 내리기
            pushDownB(bCur);
        }
    }
}

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 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();
    }
    output();
}

 

모노미노도미노 2에 비해서 추가된 조건이 하나 밖에 없어서 금방 풀 줄 알았는데 생각보다 시간이 오래 걸렸따

역시 플래티넘 문제 ..