[ BOJ 백준 1840번 - 스도쿠 ] 해설 및 코드

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

 

목적

스도쿠에 채워 넣을 번호가 81개의 줄에 걸쳐서 주어진다. 이때, 실수한 단계가 몇 번째인지 구하자.

 

접근법

1. 1~81번까지 올바른 입력인지 확인하기에는 시간제한에 걸린다. 이분탐색으로 확인할 단계 수를 줄이든, 틀린 위치부터 단계를 거슬러 올라가면서 구해야한다. 이분탐색은 72ms 정도가 걸린다. 후자의 방법은 0ms.

 

#include<iostream>
#define f(i,l,r) for(int i=l;i<=r;++i)
#define set(i,j,k,l) used[0][i][k]=used[1][j][k]=used[2][3*((i-1)/3)+1+(j-1)/3][k]=l
using namespace std;
 
int t[82][3],s[10][10]={0,},used[3][10][10]={0,};
 
bool valid(int i,int j,int k){
    return !(used[0][i][k]||used[1][j][k]||used[2][3*((i-1)/3)+1+(j-1)/3][k]);
}
 
bool fill(int i,int j){
    if(i==9&&j==10) return true;
    if(j==10)return fill(i+1,1);
    if(s[i][j]!=0)return fill(i,j+1);
    
    int ret=false;
    f(k,1,9)if(valid(i,j,k)){
        set(i,j,k,1);
        ret=fill(i,j+1);
        set(i,j,k,0);
        if(ret)break;
    }
    return ret;
}
 
int main(){
    f(i,1,81)cin>>t[i][0]>>t[i][1]>>t[i][2];
    int a,b,c,j=0;
    f(i,1,81){
        a=t[i][0],b=t[i][1],c=t[i][2];
        if(!valid(a,b,c)){
            j=i;
            while(!fill(1,1)){
                --j;
                a=t[j][0],b=t[j][1],c=t[j][2];
                s[a][b]=0;
                set(a,b,c,0);
            }
            break;
        }
        s[a][b]=c;
        set(a,b,c,1);
    }
    
    cout<<(j==0?-1:j);
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.