[BAE/<JOON> 문제풀이] 1648. 격자판 채우기

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

1648번: 격자판 채우기

서론

컨닝 풀고나니까 같은 문제라는걸 알고 풀었다. 컨닝 풀기 전에는 전혀 생각이 안났다는게 신기하다.

---

풀이

컨닝과 완전히 같은 문제인 대신 구현이 살짝 더 복잡하다.

격자판을 행으로 구분해 분할하고 각 행마다의 상태를 bitmask를 저장해 중복 계산을 피한다.

로직은 다음과 같다.

1. 현재 행에 빈칸 위치를 계산한다. ( 이전 칸에서 도미노를 세운 위치를 제외한다. ) 

2. 각 빈칸마다 뉘인 배치 / 세운 배치를 완전탐색으로 집어넣는다. 
    각 위치에 대한 비트 마스크를 별도로 만들어 해결했다.

3. 누운 배치의 경우 다음 칸에 도미노가 있는 것이 불가능하므로 이것에 대한 검사를 진행한다.

4. 정합성 검사를 통과한 경우 현재 배치에서 도미노를 세운 위치를 비트마스크로 저장하고 다음 탐색을 진행한다.

5. 마지막 행에 도착한 경우 빈 칸을 뉘인 도미노들로 채울 수 있는지 검사하여 채울 수 있는 경우 1, 없는 경우 0을 리턴한다.

 

BF 풀이에 행 / 행 상태에 대한 최적화만 집어넣었기 때문에 AC 코드 중 가장 느리다... 그래도 문제 출제자 의도에 맞춰서 맛있게 푼 것 같아서 만족스럽다. 빠른 풀이들도 찾아봐야겠다.

---

코드

#include <iostream>
#include <vector>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;
using ll = long long;
const int mod = 9901;
int n, m;
vector<vector<int>> dp; // 눕 0, 세 1 // 막줄이면 투페어 검사해서 통과하면 1 탈락이면 0 // 컨닝과 다른 점은 무조건 모든 칸을 채워야 함
int r(int row, int st) {
    int& ret = dp[row][st];
    if (ret != -1) return ret;
    if (row == n) { // 막줄이면
        int sign = 0;
        for (int i = 0; i < m; i++) {
            if(((st & (1 << i)) == 0 && (((st & (1 << (i + 1))) > 0) || i == m - 1))) { // 현재 칸이 눕인데 다음칸이 눕 아니거나 마지막 칸이면 오류
                sign = 1; break;
            }            
            else if (((st & (1 << i)) == 0 && (st & (1 << (i + 1))) == 0)) { // 연속하는 두칸이 비어있으면 넘어감
                i++; continue;
            }
        }
        return ret = 1 - sign;
    }
    ret = 0;
    vector<int> fp;
    for (int i = 0; i < m; i++) {
        if ((st & (1 << i)) == 0) { // 빈칸 추출
            fp.push_back(i);
        }
    }    
    vector<int> stch(1 << m);
    for (int i = 0; i < (1 << fp.size()); i++) {        
        if (fp.size() > 0 && fp[fp.size() - 1] == m - 1 && (i & (1 << (fp.size() - 1))) == 0) continue; // 마지막 칸에는 눕힐 수 없음
        int nst = 0; int cs = i; vector<int> ch(m); int sign = 0;
        for (int j = 0; j < fp.size(); j++) {
            if (ch[fp[j]] == 1) continue;
            if ((cs & (1 << j)) == 0) {
                if ((st & (1 << fp[j])) == 0 && (st & (1 << (fp[j] + 1))) == 0) { // 눕혀놓을 공간 있으면
                    ch[fp[j]] = 1; ch[fp[j] + 1] = 1;
                }
                else {
                    sign = 1; break; // 공간 없으면 잘못된 배치임
                }
            }            
            if ((cs & (1 << j)) > 0) {
                if ((st & (1 << fp[j])) == 0) { // 세우면 다음 줄에 영향
                    ch[fp[j]] = 1;
                    nst |= (1 << fp[j]);
                }
            }
        }
        if (stch[nst] == 1 || sign == 1) continue;
        stch[nst] = 1;
        ret += r(row + 1, nst);
        ret %= mod;
    }
    return ret;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m; 
    if (n % 2 == 1 && m % 2 == 1) {
        //cout << 0; return 0;
    }
    dp = vector<vector<int>>(n + 1, vector<int>(1 << m, -1));
    cout << r(1, 0);
    return 0;
}