백준 25331, Drop 7

개요

문제 링크
골드 5, 구현, 시뮬레이션
같은 행/열에 있는 원소 개수만큼의 값이 적힌 원소를 동시에 지울 때 가장 최적의 낙하 위치 찾기

---

접근

1. 실수하면 상당히 골머리 썩을 문제, 낙하 + 덩어리 개수세기 + 배열 변형까지 3요소가 있는 문제는 골 3에서도 많이 봐서 골3 정도로 가도 될 것 같은데 예시 설명이 너무 자세해서 골4에 투표했다.
2. 문제가 쉬워지는 건 배열 크기가 49밖에 안돼서 걍 최적화 할 방법이 생각나지 않으면 4중 루프를 돌려버리면 되기 때문이다. 하나씩 생각해보자.
   1. 우선 개수세기, 이게 한 줄당 원소 개수가 아니라 덩어리진, 즉 연속진 원소의 개수임을 잘 생각해야 한다. 그럼 덩어리 내 원소가 존재하는 왼쪽이나 위로 최대한 이동한 뒤 아래나 오른쪽 끝으로 이동하면 된다.
   2. 다음 낙하, 현재가 0이고 위가 0이 아니면 내려보내면 되는데 여기서 복잡하게 생각하지 말고 2중 포문을 49번 돌려서 모든 문제를 차단해버리자.
   3. 마지막으로 배열 변형, 현재 위치 값이 0이 아니고, 가로 또는 세로 덩어리 개수와 같으면 새로운 배열에 저장했다가 마지막에 저장된 위치를 0으로 바꿔준다. 바꾸는 것도 머리아프게 if문 쓰지말고 그냥 1로 초기화, 0을 저장했다가 곱해버리자. 이때 한 번이라도 바꿨다면 1을 return 해서 while문이 계속 돌아가게 만든다.
3. 이 세 개만 정확히 구현하고, 모든 열에 대해서 맨 위에 값을 놓고 낙하한 뒤, 변형을 할 수 있는 동안 (while) 낙하를 하고, 마지막에 0이 아닌 개수를 세서 최솟값 업데이트를 하면 된다.

---

Pseudo code

count() {
    if (horizontal) // 가로
        while(x && cur) x-- // 왼쪽끝
        while(x<n && cur) x++, cnt++ // 오른쪽 끝
    else
        // "
    return cnt
}

down() {
    for (0~49) // 100번쯤 해도 상관 없음 어차피 10000번 이내
        for (y = 2~7)
            for (x = 1~7)
                if (!cur && up)
                    cur=up, up=0
}

clear(a) {
    int c[8][8] = 1
    for (y, x)
        if (cur && cur = count(가로) || cur = count(세로))
            c[y][x] = 0
    a *= c // 0이면 사라짐
}

---

Source code

#include <bits/stdc++.h>
using namespace std;

using vec=vector<int>;
using mat=vector<vec>;
mat a(8,vec(8)),b;

int count(mat &a,int y,int x,bool d) {
    int c=0;
    if (d) {
        int i=x;
        while(i&&a[y][i]) i--;
        i++;
        while(i<=7&&a[y][i]) c++,i++;
    } else {
        int i=y;
        while(i&&a[i][x]) i--;
        i++;
        while(i<=7&&a[i][x]) c++,i++;
    }
    return c;
}
void down(mat &a) {
    for (int _=1;_<=49;_++)
        for (int i=2;i<=7;i++)
            for (int j=1;j<=7;j++)
                if (!a[i][j]&&a[i-1][j]) {
                    a[i][j]=a[i-1][j];
                    a[i-1][j]=0;
                }
}
bool clear(mat &a) {
    mat c(8,vec(8,1));
    bool r=0;
    for (int i=1;i<=7;i++)
        for (int j=1;j<=7;j++)
            if (!a[i][j]) continue;
            else if (a[i][j]==count(a,i,j,1))
                c[i][j]=0,r=1;
            else if (a[i][j]==count(a,i,j,0))
                c[i][j]=0,r=1;
    for (int i=1;i<=7;i++)
        for (int j=1;j<=7;j++)
            a[i][j]*=c[i][j];
    return r;
}

int main() {
    for (int i=1;i<=7;i++)
        for (int j=1;j<=7;j++)
            cin>>a[i][j];
    int k;cin>>k;
    int m=50;
    for (int j=1;j<=7;j++) {
        b=a;
        if (b[1][j]) continue;
        b[1][j]=k;
        down(b);
        while(clear(b)) down(b);
        int s=0;
        for (int i=1;i<=7;i++)
            for (int j=1;j<=7;j++)
                if (b[i][j]) s++;
        m=min(m,s);
    }
    cout<<m;
}