[Algorithm] 백준 2580 스도쿠 c++

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

2580번: 스도쿠

 

풀이

백트래킹

• 스도쿠를 입력받을 때 빈 칸을 vector<pair<row, col>> v에 저장한다.
• v를 통해 빈칸의 위치를 얻고, 빈칸에 1 ~ 9 사이의 숫자를 넣어본다.
• 현재 넣은 숫자가 스도쿠의 규칙을 만족한다면 다음 빈칸을 채우러 간다. (백트래킹)
• 현재 넣은 숫자가 스도쿠의 규칙을 만족하지 않는다면 그 칸을 비워준다. (0으로 초기화)
• 스도쿠의 규칙을 만족하는지의 여부는 isSetNum 함수로 판단한다. 빈칸의 위치를 기준으로 가로, 세로, 정사각형에 현재 넣은 숫자와 같은 값이 있다면 false를 반환하고, 그렇지 않다면 true를 반환한다.
• 이때 주의해야 할 것은 빈칸의 위치는 판단에서 제외시켜야 한다는 것이다. 따라서 각각의 값을 확인할 때 현재 위치를 분기처리해야 한다.
• 정사각형의 경우 9 x 9의 스도쿠를 3 x 3 박스 9개로 나누고, row / 3 * 3 col / 3 * 3으로 현재 위치가 속한 박스의 시작 위치를 구한다.
• 스도쿠의 빈칸이 모두 채워져 완성되었을 경우 결과를 출력하고, flag를 이용해 완성되었음을 알린다. 만약 flag 판단을 하지 않는다면 가능한 모든 결과를 출력하게 된다.

 

소스코드

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

int sd[9][9];
vector<pair<int, int>> v;
bool flag = false;

bool isSetNum(int row, int col){
    int cur = sd[row][col];

    //가로
    for(int i=0; i<9; i++){
        if(i == col) continue;
        if(cur == sd[row][i]) return false;
    }

    //세로
    for(int i=0; i<9; i++){
        if(i == row) continue;
        if(cur == sd[i][col]) return false;
    }

    //3x3 정사각형
    int r = row / 3;
    int c = col / 3;

    for(int i=r*3; i<r*3 + 3; i++){
        for(int j=c*3; j<c*3 + 3; j++){
            if(i == row && j == col) continue;
            if(cur == sd[i][j])    return false;
        }
    }

    return true;
}

void backtrack(int cur){
    if((int)v.size() == cur){
        for(int i=0; i<9; i++){
            for(int j=0; j<9; j++)
                cout<<sd[i][j]<<" ";
            cout<<endl;
        }
        flag = true;
        return;
    }

    for(int i=1; i<=9; i++){
        sd[v[cur].first][v[cur].second] = i; //숫자 넣기
        if(isSetNum(v[cur].first, v[cur].second)){ //현자 위치에서 위 숫자의 유효성 판단
            backtrack(cur + 1);
            if(flag) return; //스도쿠가 완성된 경우 종료
        }
        sd[v[cur].first][v[cur].second] = 0; //유효한 숫자가 아닌 경우 값 비워주기
    }
}

int main(){
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            cin>>sd[i][j];
            if(!sd[i][j])
                v.push_back(make_pair(i, j));
        }
    }

    backtrack(0);

    return 0;
}

 

🤐사족

처음에는 현재 위치를 기준으로 가로, 세로, 정사각형 각각에서 없는 숫자를 넣어주려고 했다. 이렇게 하면 숫자를 미리 넣고 가능한지 아닌지 판단하는 지금 코드보다 복잡해지고 백트래킹의 의미도 애매해진다. 혼자 힘으로 풀기에는 주어진 예시가 너무 적어 다음 블로그의 도움을 받았다. 예시가 2개나 더 있다!