문제링크 입니다

[KAKURO2] 문제 😭😭😭😭😭😭

KAKURO2

카쿠로는 흔히 십자말풀이 수학 버전이라고 불리는 논리 퍼즐이다. 카쿠로는 위와 같이 생긴 정사각형의 게임판을 가지고 하는 퍼즐로, 이 게임판의 각 칸은 흰 칸이거나, 검은 칸이거나, 힌트 칸이다. (힌트 칸은, 대각선으로 갈라져 있고 숫자가 씌여 있는 칸을 말한다) 모든 흰 칸에 적절히 숫자를 채워 넣어 규칙을 만족시키는 것이 이 게임의 목표이다.

카쿠로의 규칙은 다음과 같다.

  • 모든 흰 칸에는 1 부터 9 까지의 정수를 써넣어야 한다.
  • 세로로 연속한 흰 칸들의 수를 모두 더하면, 그 칸들의 바로 위에 있는 힌트 칸의 왼쪽 아래에 씌인 숫자가 나와야 한다.
  • 가로로 연속한 흰 칸들의 수를 모두 더하면, 그 칸들의 바로 왼쪽에 있는 힌트 칸의 오른쪽 위에 씌인 숫자가 나와야 한다.
  • 이 때 한 줄을 이루는 연속된 흰 칸들에는 같은 수를 두 번 넣을 수 없다. 예를 들어, 두 개의 흰 칸의 숫자를 더해서 4가 나와야 한다고 하면, 1+3=4 이거나 3+1=4 만이 가능하고, 2+2=4 는 불가능하다.

[풀이]

책이 아니였으면 못 풀었을 문제…. 이 문제를 빠르게 해결하기 위해 비트마스크를 또 사용하였습니다.
getSize , getSum 함수를 에서 각 mask의 원소 개수와 mask에 속한 원소들의 합을 리턴합니다.
각 칸에 들어갈 수 잇는 후보 숫자들의 목록을 저장하는 ‘candidates[len][sum][known]’ 을 선언하고 초기화를 위해 generateCandidates 함수를 구현해야 했습니다.
빠르게 해결하기 위해 필요한 정보(ex. 각 칸의 색, 각 흰 칸에 쓴 숫자.)들을 미리 최대크기의 배열로 선언하고 정보를 저장해놓습니다.
getCandint 함수와, getCandCoord함수를 이용하여 좌표가 주어지면 해당 힌트들을 이용하여 가능한 후보들의 집합(candidates)을 반환합니다.
마지막으로 이전에 해왔던 것 처럼 search()를 구현하여 문제를 해결합니다. 세부 내용은 코드에 설명되어 있습니다.

입력

입력의 첫 줄에 테스트 케이스의 수 C ( C <= 50)가 주어진다.

각 테스트 케이스의 첫 줄에는 카쿠로 게임판의 크기 N (1 <= N <= 20) 이 주어진다. 카쿠로 게임판은 언제나 정사각형이다. 그 후 N줄에, 각 N개의 정수로 카쿠로 퍼즐의 해답이 주어진다. 힌트 칸이나 검은 칸은 0 으로 주어지고, 흰 칸은 해당 칸에 들어갈 숫자로 주어진다.

출력

각 테스트 케이스마다 n 줄에 각 n개의 숫자로 모두 채워진 게임판을 출력합니다. 검은 칸이나 힌트 칸은 0으로 표시합니다.

입력 예제

1
8
0 0 0 0 0 0 0 0
0 1 1 0 0 1 1 1
0 1 1 0 1 1 1 1
0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0
0 0 0 1 1 1 1 1
0 1 1 1 1 0 1 1
0 1 1 1 0 0 1 1
24
2 1 0 16
2 5 0 24
3 1 0 17
3 4 0 29
4 1 0 35
5 2 0 7
5 5 0 8
6 3 0 16
7 1 0 21
7 6 0 5
8 1 0 6
8 6 0 3
1 2 1 23
1 3 1 30
1 6 1 27
1 7 1 12
1 8 1 16
2 5 1 17
3 4 1 15
4 7 1 12
5 5 1 7
5 8 1 7
6 2 1 11
6 3 1 10

출력 예제

0 0 0 0 0 0 0 0
0 9 7 0 0 8 7 9
0 8 9 0 8 9 5 7
0 6 8 5 9 7 0 0
0 0 6 1 0 2 6 0
0 0 0 4 6 1 3 2
0 8 9 3 1 0 1 4
0 3 1 2 0 0 2 1

전체 코드는 다음과 같습니다.

//
//  KAKURO2.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/11/02.
//

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

ifstream fin("KAKURO2.txt");

void initialization();
int n; // 게임판의 크기
const int MAXN = 20;
/*
제약전파 : 한곳을 채우면 다른한곳을 쉽게 채울 수 있다.
채울 순서 정하기 : 적은 수로 구현할 수 있는 것부터.
후보의 수 계산하기 : getCandidate() 힌트에 해당하는 후보숫자들의 목록을 반환하는 함수 구현
후보의 수 빠르게 계산하기 getCandidate()을 좀더 효율적으로 구현하는 generateCandidates()구현
 */

// mask에 속한 원소들의 개수 반환
int getSize(int mask){
    int num = 0, compare = 1;
            for (int i = 1; i <= 9; ++i)
            {
                   compare = compare << 1;
                   if (compare & mask) num++;
            }
            return num;


    //return __builtin_popcount(mask);
}

// mask에 속한 원소들의 합을 반환
int getSum(int mask){
    int sum=0;
    for(int i=0; i<10; i++)
        if (mask & (1 << i)){
            sum += i;
        }
    return sum;
}
/*
int getCandidate(int len, int sum, int known){
    // 조건에 부합하는 집합들의 교집합
    int allSets = 0;
    for(int set=2; set<1024; set = set+2){
        if((set&known) && (getSize(set)==len) && getSum(set)==sum){
            allSets |= set;
        }
    }
    return (allSets&~known);
}
 */
// len / sum / known
int candidates[10][46][1024];

void generateCandidates(){
    memset(candidates, 0, sizeof(candidates));
    for(int set=0; set< 1024; set+=2){
        int length = getSize(set);
        int sum = getSum(set);
        int subset = set;
        while(true){
            candidates[length][sum][subset] |= (set &~subset);
            if(subset == 0) break;
            subset = (subset - 1) & set;
        }
    }
}
// 게임판의 정보
// 카쿠로의 조합 탐색을 위한 유틸리티 함수들
// color : 각 칸의 색깔(0 : 검은칸 혹은 힌트칸, 1 = 흰칸)
// value: 각 흰 칸에 쓴 숫자(아직 쓰지 않은 칸은 0)
// hint : 각 칸에 해당하는 두 힌트의 번호
int color[MAXN][MAXN], value[MAXN][MAXN], hint[MAXN][MAXN][2];
// 각 힌트의 정보
// sum   : 힌트 칸에 쓰인 숫자
// length: 힌트 칸에 해당하는 힌 칸의 수
// known : 힌트 칸에 해당하는 흰 칸에 쓰인 숫자들의 집합
int q, sum[MAXN*MAXN], length[MAXN*MAXN], known[MAXN*MAXN];
//( y,x) 에 val을 쓴다.
void put(int y, int x, int val){
    for(int h=0; h<2; h++){
        known[hint[y][x][h]] += (1<<val);
    }
    value[y][x] = val;
}
// (y,x) 에 쓴 val을 지운다.
void remove(int y, int x, int val){
    for(int h=0; h<2; h++){
        known[hint[y][x][h]] -= (1<<val);
    }
    value[y][x] = 0;
}
// 힌트 번호가 주어질 때 후보의 집합을 반환한다.
int getCandHint(int hint){
    return candidates[length[hint]][sum[hint]][known[hint]];
}
// 좌표가 주어질 때 해당 칸에 들어갈 수 있는 후보의 집합을 반환한다.
int getCandCoord(int y, int x){
    return getCandHint(hint[y][x][0]) & getCandHint(hint[y][x][1]);
}
void printSolution(){
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cout << value[i][j] << " ";
        }
        cout << endl;
    }
}
// 실제 탐색
// 11. 14 todo
bool search(){
    // 아직 숫자가 쓰지 않은 흰 칸 중에서 후보의 수가 최소인 칸을 찾는다.
    int y= -1, x = -1, minCands = 1023;
    for(int i=0; i <n; i++){
        for(int j=0; j<n; j++){
            if(color[i][j]==1 && value[i][j] == 0){
                int cands = getCandCoord(i,j);
                if(getSize(minCands) > getSize(cands)){
                    minCands = cands;
                    y = i;
                    x = j;
                }
            }
        }
        if(minCands == 0) return false;
    }
    // 모든 칸이 채워졌으면
    if(y ==-1){
        printSolution();
        return true;
    }
    // 칸을 채운다.
    for(int val = 1; val <=9; val++){
        if(minCands &(1<<val)){
            put(y,x,val);
            if(search()) return true;
            remove(y,x,val);
        }
    }
    return false;
}

void read(){
    fin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            fin >> color[i][j];
        }
    }
    int hintNum;
    fin >> hintNum;
    int y,x,direction;

    // 0은 가로 힌트, 1은 세로힌트를 의미
    int dy[2] = { 0, 1 };
    int dx[2] = { 1, 0 };
    for(int i=0; i<hintNum; i++){
        fin >> y >> x >> direction >> sum[i];
        y--;
        x--;
        length[i]=0;
        while(true) {
            // 벽을 만날떄 까지 계속 ~
            y += dy[direction]; x += dx[direction];
            if(y >= n || x >= n || color[y][x] == 0) break;
            hint[y][x][direction] = i;
            length[i]++;
        }
    }

}
int main(){
    int test_case;
    fin >> test_case;
    generateCandidates();

    for(int test =0; test<test_case; test++){
        initialization();
        read();
        search();
    }
}
void initialization(){
    memset(color, 0, sizeof(color));
    memset(value, 0, sizeof(value));
    memset(hint, 0, sizeof(hint));
    memset(sum, 0, sizeof(sum));
    memset(length, 0, sizeof(length));
    memset(known, 0, sizeof(known));
}

KAKURO2

Comments