[SWEA] 2891번 분수 스도쿠

2891번 분수 스도쿠

문제 링크

 

해결방법

스도쿠의 빈 칸에 1~9 까지의 수를 대입해가며 모든 경우를 탐색하는 완전 탐색 문제이다

 

 

⭐️ 솔루션 ⭐️

스도쿠 한칸을 pair 로 선언하여 입력받는다

• 빈칸인 경우 0으로, 아닌 경우 입력값으로 분수를 채운다
• 이 때, 분수인 경우와 정수인 경우를 나눠야한다
• 만약 분수라면 분모와 분자를, 정수라면 분모만 입력받고 분자는 10으로 채워준다

 

이제 탐색을 수행한다

• 빈 칸에 대해 1~9 까지의 수를 모두 대입해본다
• 이 때, 가로•세로•스도쿠•분수 조건 을 체크한 뒤, 모두 만족한 경우 숫자를 대입해준다
• 이러한 방식으로 백트래킹을 통해 모든 경우를 탐색한다

 

문제 조건

• 6x6 보드가 주어지며, 3x2 스도쿠가 총 6개 존재한다
• 분수의 크기는 1보다 작아야하기 때문에, 분자 < 분모 의 조건을 가진다

 

 

소스코드

문제 해결 시간 : 1h 40m

메모리 : 12636 KB

시간 : 101 ms

#include <iostream>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

struct node {
    int x,y,p;
    
    node() { }
    node(int _x,int _y,int _p) : x(_x),y(_y),p(_p) { }
};

struct num {
    int top,bottom;
    
    num() { }
    num(int _top,int _bottom) : top(_top),bottom(_bottom) { }
};

int testcase;
int n,ans,blank;
string str;

num map[6][6];

vector<node> v;

// 스도쿠 출력
void printSudoku(){
    for(int i=0; i<6; i++){
        for(int j=0; j<6; j++){
            if(map[i][j].bottom == 10){
                cout << map[i][j].top << " ";
            }else{
                cout << map[i][j].top << "/" << map[i][j].bottom << " ";
            }
        }
        cout << "\n";
    }
}

// 3x2 스도쿠의 시작 행 반환
int getRow(int i){
    if(i==0 || i==1)
        return 0;
    else if(i==2 || i==3)
        return 2;
    else
        return 4;
}

// 3x2 스도쿠의 시작 열 반환
int getCol(int j){
    if(j==0 || j==1 || j==2)
        return 0;
    else
        return 3;
}

// 가로, 세로, 3x2, 분수조건을 확인하는 함수
bool chkSudoku(int r,int c,int p,int number){
    bool row = true;
    bool col = true;
    bool box = true;
    bool dist = true;
    
    // 가로(열) 확인
    for(int i=0; i<6; i++){
        if(map[i][c].top == number || map[i][c].bottom == number){
            row = false;
            break;
        }
    }
    
    // 세로(행) 확인
    for(int j=0; j<6; j++){
        if(map[r][j].top == number || map[r][j].bottom == number){
            col = false;
            break;
        }
    }
    
    // 스도쿠(3x2) 확인
    int rr = getRow(r);
    int cc = getCol(c);
    
    for(int i=rr; i<=rr+1; i++){
        for(int j=cc; j<=cc+2; j++){
            if(map[i][j].top == number || map[i][j].bottom == number){
                box = false;
                break;
            }
        }
        if(!box) break;
    }
    
    // '분자 > 분모' 확인
    if(p==0 && map[r][c].bottom!=0){
        if(number > map[r][c].bottom)
            dist = false;
    }
    if(p==1){
        if(map[r][c].top > number)
            dist = false;
    }
    
    // 4가지 조건을 모두 만족한다면 True 반환
    if(row && col && box && dist)
        return true;
    else
        return false;
}

// DFS 탐색
void dfs(int ind,int cnt){
    // 정답을 찾은 경우
    if(cnt == v.size()){
        printSudoku();
        return;
    }
    
    // 탐색 진행
    int x = v[ind].x;
    int y = v[ind].y;
    int p = v[ind].p;
    
    // 1~9 까지의 수를 넣어봄
    for(int k=1; k<=9; k++){
        // 분모는 1이 올 수 없음
        if(p==1 && k==1) continue;
        
        if(chkSudoku(x,y,p,k)){
            if(p==0) map[x][y].top = k;
            else map[x][y].bottom = k;
            
            dfs(ind+1,cnt+1);
            
            if(p==0) map[x][y].top = 0;
            else map[x][y].bottom = 0;
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int t=1; t<=testcase; t++){
        // 초기화
        ans = 0;
        blank = 0;
        v.clear();
        
        // 입력
        for(int i=0; i<6; i++){
            for(int j=0; j<6; j++){
                cin >> str;
                
                // 분수 입력
                if(str.size() > 1){
                    int t,b;
                    if(str[0] == '-'){
                        t = 0;
                        blank++;
                        v.push_back(node(i,j,0));
                    }else{
                        t = str[0] - '0';
                    }
                    
                    if(str[2] == '-'){
                        b = 0;
                        blank++;
                        v.push_back(node(i,j,1));
                    }else{
                        b = str[2] - '0';
                    }
                    
                    map[i][j] = num(t,b);
                }
                // 숫자 입력
                else{
                    if(str == "-"){
                        map[i][j] = num(0,10);
                        blank++;
                        v.push_back(node(i,j,0));
                    }else{
                        map[i][j] = num(stoi(str),10);
                    }
                }
            }
        }
        
        // 탐색 시작
        cout << "#" << t << "\n";
        dfs(0,0);
    }
    
    return 0;
}