[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));
}
Comments