KAKURO2 (최상, p. 434)

문제#

어떻게 풀었나?#

지금까지 책을 보고 푼 문제는 있어도 처음부터 끝까지 보고 푼 문제는 없었는데, 이 문제는 처음부터 끝까지 책만 보고 풀어서 책 내용을 요약해서 정리해보려고 한다.

핵심 2가지#

이 문제는 CSP문제(제약 충족 문제)로 DFS로 풀어야 한다는 것을 먼저 파악해야 한다.
CSP문제는 제약 전파 방식과 탐색 순서를 어떻게 가져갈 것인지가 가장 중요하다.
1. 현재 칸에 대해 정답을 설정하면 다른 칸에서 설정할 수 있는 정답의 선택지가 줄어들게 되는데 이렇게 줄어들게 되는 선택지를 다른 칸에 어떻게 전달할 것인지를 잘 생각해야 한다. 뒤에서 얘기하겠지만, 이런 것을 제약 전파라 한다.
2. DFS 탐색 순서를 어떻게 하는 것이 좋을지 생각해야 한다. 카쿠로에서 이것은 상당히 자명한데, 손으로 직접 카쿠로를 풀어보면 힌트에 해당하는 칸의 수가 작은 것부터 채우는게 유리함을 금방 눈치 챌 수 있다. 문제는.. 이것을 코드로 어떻게 구현해내는가일 것이다.

제약 충족 문제 (CSP: Constraint Satisfaction Problem)#

카쿠로는 답이 하나뿐이므로 최적화 문제가 아니다. 카쿠로와 같이 특정 제약에 해당하는 답을 찾는 문제를 제약 충족 문제라고 한다. → 최적화 문제가 아니므로 DP나 Greedy로 접근하면 안되고, 제약 조건을 얼마나 강하게 줄이느냐가 관건이다. 스도쿠, N-퀸 문제등이 CSP문제에 해당한다. CSP문제에서는 크게 2가지(제약 전파, 채울 순서 정하기)만 신경쓰면 된다.

※ 최적화 문제란?#

여러 해 중에 문제에서 요구하는 조건을 만족하는 가장 좋은 해를 고르는 문제

※ 왜 최적화 문제가 아닌 카쿠로와 같은 문제는 DP나 Greedy로 접근하는 것이 좋지 않은가?#

DP의 본질

큰 문제의 최적해가 작은 문제의 최적해 조합으로 표현된다.
Greedy의 본질

지금 이 순간의 최선 선택이 전체에서도 최선임을 증명할 수 있을 때만 가능

→ 즉, 최적이나 최선이라는 뜻은 비교 기준이 있다는 뜻으로 두 방법 다 무엇이 더 좋은가를 비교하는 알고리즘 이다.

그런데 카쿠로나 스도쿠에 ‘비교’가 있나? → 없다. 카쿠로는 조건을 만족하기만 하면 되지, 조건을 만족하는 더 나은 해를 구하는 것이 아니다.

1) 카쿠로 문제에서의 제약 전파 방법#

(x,y)에 val라는 값을 채워넣으면 (x,y)와 연관있는 왼쪽, 위쪽 힌트들의 이미 정해진 값 list인 known[]에 val를 기록 한다. 그리고 나중에 다른 (p,q)좌표가 위에서 업데이트한 힌트와 연관이 있다면, known[]을 보고 val라는 값을 제외해야 한다는 제약을 전파받을 수 있다.

2) 카쿠로 문제에서의 탐색 순서 정하기#

처음에 언급했듯이 힌트가 담당하는 칸 수가 적은 순서대로 채워나가는 것이 좋다는 것은 매우 자명하다. 그럼 힌트별로 남아있는 칸수를 적어놓고, 칸수가 가장 적은 칸을 선택한 다음 해당 칸에 쓸 수있는 값들을 적는 것으로 DFS를 돌면 될 것이다.

자, 이제 가장 큰 문제는 ‘위의 방법들을 어떻게 빠르게 할 것이냐’ 이다. 현재 칸에 어떤 값을 적을 때 힌트를 참고하여 가능한 후보 값들을 파악해야 하는데, 이걸 빠르게 하는 것이 쉽지 않다. 우선, ①known[]에 적힌 값과 ②채워야 하는 칸 수, ③힌트에 적힌 값을 보고 가능한 후보 값들을 파악할 수 있다는 걸 파악해야 한다. 그러고 나면, 방금 언급한 3가지 상태에 대한 답은 항상 불변이므로, 이 결과 값들에 대해 DP로 답을 먼저 구해놓으면 된다.

정답 코드#

#include <bits/stdc++.h>
using namespace std;
const int BLACK = 0;
const int WHITE = 1;
int n;
int board[21][21];
int value[21][21];
int hno_by_co[21][21][2];

int sum_by_hno[21*21*2];
int cnt_by_hno[21*21*2];
int known_by_hno[21*21*2];

void Init(int n) {
    memset(value, 0, sizeof(value));
    memset(known_by_hno, 0, sizeof(known_by_hno));
}

void CalcHnoInfo(int x, int y, int dir) {
    int hint_no = hno_by_co[x][y][dir];
    cnt_by_hno[hint_no]=0;
    known_by_hno[hint_no]=0;
    if(dir == 0) {
        for(int i=y+1; i<n; i++) {
            if(board[x][i] == BLACK) return;
            hno_by_co[x][i][dir] = hint_no;
            cnt_by_hno[hint_no]++;
        }
    }
    else {
        for(int i=x+1; i<n; i++) {
            if(board[i][y] == BLACK) return;
            hno_by_co[i][y][dir] = hint_no;
            cnt_by_hno[hint_no]++;
        }
    }
}

int candidates[46][21][1023]; //[hint_sum][cnt][known_values]
int sum_dp[1023];
int cnt_dp[1023];
int GetSum(int sum_bit) {
    if(sum_bit==0) return 0;
    if(sum_dp[sum_bit]>=0) return sum_dp[sum_bit];

    int & ret = sum_dp[sum_bit];
    ret=0;
    for(int i=1; i<10; i++) {
        if(sum_bit & (1<<i)) ret += i;
    }
    return ret;
}
int GetCnt(int sum_bit) {
    if(sum_bit==0) return 0;
    if(cnt_dp[sum_bit]>=0) return cnt_dp[sum_bit];

    int & ret = cnt_dp[sum_bit];
    ret=0;
    for(int i=1; i<10; i++) {
        if(sum_bit & (1<<i)) ret++;
    }
    return ret;
}
void GenerateCandidates() {
    for(int s=0; s<=1022; s+=2) {
        int sum = GetSum(s);
        int cnt = GetCnt(s);
        for(int known=s; ; known = (known-1)&s) {
            candidates[sum][cnt][known] |= (s & ~known);
            if(known==0) break;
        }
    }
}

inline int GetCandidatesByHno(int hno) {
    return candidates[sum_by_hno[hno]][cnt_by_hno[hno]][known_by_hno[hno]];
}

inline int GetCandidatesByCo(int x, int y) {
    return GetCandidatesByHno(hno_by_co[x][y][0]) & GetCandidatesByHno(hno_by_co[x][y][1]);
}

const int INF = 0x3f3f3f3f;
const int NA = -1;
bool dfs() {
    int mn_len=INF, mn_x=NA, mn_y=NA;
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            if(board[i][j]==WHITE && value[i][j]==0) {
                int cnt = GetCnt(GetCandidatesByCo(i,j));
                if(mn_len > cnt) {
                    mn_len = cnt;
                    mn_x=i, mn_y=j;
                }
            }
        }
    }

    if(mn_len==0) return false; //No Answer
    if(mn_len==INF) {
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                printf("%d ", value[i][j]);
            }
            puts("");
        }
        return true;
    }

    int candi = GetCandidatesByCo(mn_x, mn_y)>>1;
    int cnt=1;
    while(candi) {
        if(candi&1) {
            value[mn_x][mn_y] = cnt;
            known_by_hno[hno_by_co[mn_x][mn_y][0]] |= (1<<cnt);
            known_by_hno[hno_by_co[mn_x][mn_y][1]] |= (1<<cnt);
            if(dfs()) return true;
            value[mn_x][mn_y] = 0;
            known_by_hno[hno_by_co[mn_x][mn_y][0]] ^= (1<<cnt);
            known_by_hno[hno_by_co[mn_x][mn_y][1]] ^= (1<<cnt);
        }
        candi>>=1;
        cnt++;
    }
    return false;
}

int main() {
    memset(sum_dp, -1, sizeof(sum_dp));
    memset(cnt_dp, -1, sizeof(sum_dp));
    GenerateCandidates();
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        cin >> n;
        Init(n);
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                cin >> board[i][j];
            }
        }

        int q; cin >> q;
        for(int i=0; i<q; i++) {
            int x,y,dir,sum;
            cin >> x >> y >> dir >> sum;
            x--; y--;
            hno_by_co[x][y][dir] = i;
            sum_by_hno[i] = sum;
            CalcHnoInfo(x,y,dir);
        }

        dfs();
    }
    return 0;
}

Comment#

정말 많은 기법을 배울 수 있었고, 특히 사내 Expert 유형의 문제가 이런 조합 탐색이 많이 나와서 큰 도움이 될 것 같았다. 특히 bit연산 관련 트릭이 있어 따로 정리하였다. 부분집합 열거 비트트릭