글 읽기 - [cpp] 2580 스도쿠 문제 반례를 못찾겠습니다.

hyj2508 4년 전 0

구글에서 찾은 모든 스도쿠 코드들도 정상작동하는데 대체 어느 케이스에서 실패하는지 모르겠네요.. ㅠㅠ

도움주시면 정말 감사하겠습니다 ㅠ

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int arr[9][9];
int visited[9][9];
vector<pair<int, int>> v;

bool check_row(int x, int y, int index){
    for(int i=0;i<9;i++){
        if(index==arr[x][i]) return false;
    }
    return true;
}

bool check_column(int x, int y, int index){
    for(int i=0;i<9;i++){
        if(index==arr[i][y]) return false;
    }
    return true;
}

bool check_square(int x, int y, int index){
    int xstart_ind = (x/3)*3;
    int ystart_ind = (y/3)*3;
    for(int i=xstart_ind;i<xstart_ind+3;i++){
        for(int j=ystart_ind; j<ystart_ind+3;j++){
            if(index==arr[i][j]) return false;
        }
    }
    return true;
}

bool dfs(int x, int y, int n){
    if(n==v.size()+1) {
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                cout<<arr[i][j]<<" ";
            }
            cout<<'\n';
        }
        exit(0);
    }
    int fl=0;
    for(int i=1;i<=9;i++){
        if(check_row(x,y,i) && check_column(x,y,i) && check_square(x,y,i)){
            arr[x][y]=i;
            pair<int, int> newcor = v[n];
            if(!dfs(newcor.first, newcor.second, n+1)){
                arr[x][y]=0;
            } else {
                return true;
            }
            fl=1;
        }
    }
    if(fl==0) {
            arr[x][y]=0;
            return false;
    }
}
int main()
{
    // freopen("input.txt","r",stdin);
    int fl;
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            scanf("%1d", &arr[i][j]);
            if(arr[i][j]==0) v.push_back(make_pair(i,j));
        }
    }
    if(v.size()==0){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                cout<<arr[i][j]<<" ";
            }
            cout<<'\n';
        }
    } else {
        dfs(v[0].first, v[0].second, 1);
    }
    return 0;
}

djm03178 4년 전 0

fl이 0이 아닐 때의 리턴값이 명시되어 있지 않습니다. 61번째 줄 뒤에 return false; 만 추가하면 통과됩니다.

hyj2508 4년 전 0

와.. 진짜네요.. 제가 코드를 바꾸면서 fl 이 의미가 없어졌네요 감사합니당 ㅠㅠ

그런데 혹시 제가 본문에 작성한 코드에서 통과되지 않는 테스트케이스가 뭐가 있을지 여쭤봐도 될까요?

djm03178 4년 전 0

뭘 반환할지 명시하지 않았기 때문에 어떻게 동작할지 알 수 없을 뿐입니다. 굳이 가능성이 높은 것을 찾자면, 아무것도 리턴하지 않았는데 실제로는 true가 리턴된 것처럼 행동하면서 50번째 줄의 if가 거짓이 되었을 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[cpp] 2580 스도쿠 문제 반례를 못찾겠습니다.

hyj2508 4년 전 0

djm03178 4년 전 0

hyj2508 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말