[DFS, 백트래킹] BOJ 2239, 2580 스도쿠 (C++)

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

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

2239번: 스도쿠

2580번: 스도쿠

 

문제 해결 알고리즘

 

이 두개의 문제가 결이 같아서 같이 정리한다.

 

우선 입력을 받을 때 빈 칸의 좌표들을 전부 배열에 담고 그 배열 순서대로 1부터 9까지 입력을한다.

 

이 때, 스도쿠 규칙에 맞다면 다음 좌표로 넘어가서 거기서도 순서대로 숫자를 넣는다.

 

이 방식으로 깊이 우선 탐색을 실시해주면 된다.

 

여기서 스도쿠 규칙을 정할 때, 

 

bool horizontal(int x, int y){

    //중복 체크
    vector<bool> v(10);

    for(int i=0;i<9;i++){
        if(sudok[x][i] == 0) continue;

        if(v[sudok[x][i]]) return false;
        else v[sudok[x][i]] = true;
    }

    return true;
}

bool vertical(int x, int y){

    //중복 체크
    vector<bool> v(10);

    for(int i=0;i<9;i++){
        if(sudok[i][y] == 0) continue;

        if(v[sudok[i][y]]) return false;
        else v[sudok[i][y]] = true;
    }

    return true;
}

bool square(int x, int y){
    int start_x = x/3 * 3;
    int start_y = y/3 * 3;

    vector<bool> v(10);

    for(int i=start_x;i<start_x+3;i++){
        for(int j=start_y;j<start_y+3;j++){
            if(sudok[i][j] == 0) continue;

            if(v[sudok[i][j]]) return false;
            else v[sudok[i][j]] = true;
        }
    }

    return true;
}

 

이런 식으로 세로 가로 네모 따로따로 나눠서 조건을 체크해주었는데 틀려서 아래의 코드 처럼 하나의 함수로 체크를 해줘야 시간초과가 나지 않는다.

그리고 만약 1부터 9까지 전부 돌렸는데 해를 구하지 못했다면 다시 0으로 바꿔줘야한다.

 

 

소스 코드

 

2239번 문제 소스코드

#include <bits/stdc++.h>
using namespace std;

int sudok[9][9];
bool flag = false;
vector<pair<int, int>> emptySquare;

bool sudokCheck(int x, int y){

    //세로, 가로
    for(int i=0;i<9;i++){
        if(sudok[i][y] == sudok[x][y] && i != x) return false;
        if(sudok[x][i] == sudok[x][y] && i != y) return false;
    }

    int start_x = x/3 * 3;
    int start_y = y/3 * 3;

    //네모
    for(int i=start_x;i<start_x+3;i++){
        for(int j=start_y;j<start_y+3;j++){

            if(sudok[i][j] == sudok[x][y] && i != x && j != y) return false;

        }
    }

    return true;
}

void dfs(int idx){

    if(idx == emptySquare.size()){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                cout << sudok[i][j];
            }
            cout << '\n';
        }
        flag = true;
        return;
    }

    int x = emptySquare[idx].first;
    int y = emptySquare[idx].second;

    for(int i=1;i<=9;i++){
        sudok[x][y] = i;

        //스도쿠 만족하는지
        if(sudokCheck(x, y)){
            dfs(idx+1);
        }
        if(flag) return;
    }

    //최적의 해를 구하지 못했을 경우 다시 0 입력
    sudok[x][y] = 0;

}

int main(){
    
    // 스도쿠 판 입력
    for(int i=0;i<9;i++){
        string str; cin >> str;

        for(int j=0;j<9;j++){
            sudok[i][j] = str[j] - '0';
            if(sudok[i][j] == 0) emptySquare.push_back({i, j});
        }

    }

    dfs(0);
}

 

2580번 문제 소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int sudok[9][9];
bool flag = false;
vector<pair<int, int>> emptySquare;

bool sudokCheck(int x, int y){

    //세로, 가로
    for(int i=0;i<9;i++){
        if(sudok[i][y] == sudok[x][y] && i != x) return false;
        if(sudok[x][i] == sudok[x][y] && i != y) return false;
    }

    int start_x = x/3 * 3;
    int start_y = y/3 * 3;

    //네모
    for(int i=start_x;i<start_x+3;i++){
        for(int j=start_y;j<start_y+3;j++){

            if(sudok[i][j] == sudok[x][y] && i != x && j != y) return false;

        }
    }

    return true;
}

void dfs(int idx){

    if(idx == emptySquare.size()){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                cout << sudok[i][j] << ' ';
            }
            cout << '\n';
        }
        flag = true;
        return;
    }

    int x = emptySquare[idx].first;
    int y = emptySquare[idx].second;

    for(int i=1;i<=9;i++){
        sudok[x][y] = i;

        //스도쿠 만족하는지
        if(sudokCheck(x, y)){
            dfs(idx+1);
        }
        if(flag) return;
    }

    //최적의 해를 구하지 못했을 경우 다시 0 입력
    sudok[x][y] = 0;

}

int main(){
    
    // 스도쿠 판 입력
    for(int i=0;i<9;i++){

        for(int j=0;j<9;j++){
            cin >> sudok[i][j];
            if(sudok[i][j] == 0) emptySquare.push_back({i, j});
        }

    }

    dfs(0);
}