백준 2580 - 스도쿠 (c++)

백준 2580 - 스도쿠

문제 링크

생각 및 접근

• 백 트래킹 방식으로 해결하고자 했다. 스도쿠 빈 칸에 1부터 9까지 숫자를 넣고, 그 숫자가 promising한지 검사 후, promising하다면 스도쿠의 답으로 인정하고, promising하지 않다면 다음 숫자를 검사하거나, 모든 숫자를 검사했다면 그 전 백 트래킹 함수로 돌아가 다른 답을 찾는다.
• 빈 칸을 기억하고 있는 vector<pair<int, int>> zero;를 선언하였고, 그 벡터의 크기인 zeroNum을 저장해 두었다.
• 함수 bt의 파라미터는 벡터 zero에서 index level 까지 답을 찾았다 라는 의미다. 따라서, bt가 멈추는 조건도 if(level == zeroNum - 1)라고 정의할 수 있겠다. if(level == zeroNum - 1)이면 zero에 들어있던 모든 빈칸에 대한 답을 찾은 것 이므로, print해주고 exit(0)해주면 된다. 문제의 조건이 여러 답 중에 하나만 출력하면 되므로 제일 먼저 찾은 것을 출력했다.
• 다음 코드는 답을 찾기 위한 과정이다.

    for(int i = 1; i <= LENGTH; i++){
        sudoku[zero[level + 1].first][zero[level + 1].second] = i;
        if(promising(zero[level + 1].first, zero[level + 1].second)){
            bt(level + 1);
        }
        sudoku[zero[level + 1].first][zero[level + 1].second] = 0;
    }

  • i는 zero[level + 1]에 새로 들어갈 수 있는 값을 찾기 위해 탐색하는 변수이다. i는 1부터 9까지 돌면서 zero[level + 1]에 들어갈 수 있는 값인 지 확인하기 위해, 함수 bool promising(int a, int b) 를 선언하였다.
• bool promising(int a, int b)
  • 스도쿠에 새 답을 넣을 때, 다음 3가지 조건을 만족해야 한다.
    • 가로에 겹치는 숫자가 없는지
    • 세로에 겹치는 숫자가 없는지
    • 네모에 겹치는 숫자가 없는지
      이를 검사하는 함수가 promising이 되겠다.
  • bt에서 promising(zero[level + 1].first, zero[level + 1].second)를 호출하면 promising은 zero[level + 1]에 i가 들어갈 수 있는지 검사한다.
  • 필자는 스도쿠 각각의 가로, 세로, 네모에 숫자가 몇개 들어있는 지 세어서, 만일 그 숫자가 2를 넘는다면 return false, 모든 숫자가 2를 넘지 않는다면 return true하였다.
• int square(int a, bool en)
  • 내 index가 어느 네모에 속하는 지 확인하고, 네모의 index를 반환하기 위한 함수인데, 네모 범위를 구하는 것이 쉽게 떠오르지 않아 따로 함수를 구현했다.

코드

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

int sudoku[10][10], zeroNum;
vector<pair<int, int>> zero;

int square(int a, bool en){
    if(a >= 1 && a <= 3){
        if(en)    return 3;
        else    return 1;
    }
    if(a >= 4 && a <= 6){
        if(en)    return 6;
        else    return 4;
    }
    if(a >= 7 && a <= 9){
        if(en)    return 9;
        else    return 7;
    }
}

bool promising(int a, int b){
    int cntA[10] = {0, }, cntB[10] = {0, }, cntSquare[10] = {0, };

    for(int i = 1; i <= LENGTH; i++){
        cntA[sudoku[a][i]]++;
        cntB[sudoku[i][b]]++;
    }

    for(int i = square(a, 0); i <= square(a, 1); i++){
        for(int j = square(b, 0); j <= square(b, 1); j++){
            cntSquare[sudoku[i][j]]++;
        }
    }

    for(int i = 1; i <= LENGTH; i++){
        if(cntA[i] >= 2 || cntB[i] >= 2 || cntSquare[i] >= 2){
            return false;
        }
    }
    return true;
}

void bt(int level){
    if(level == zeroNum - 1){
        for(int i = 1; i <= LENGTH; i++){
            for(int j = 1; j <= LENGTH; j++){
                cout << sudoku[i][j] << " ";
            }
            cout << endl;
        }
        exit(0);
    }
    else {
        for(int i = 1; i <= LENGTH; i++){
            sudoku[zero[level + 1].first][zero[level + 1].second] = i;
            if(promising(zero[level + 1].first, zero[level + 1].second)){
                bt(level + 1);
            }
            sudoku[zero[level + 1].first][zero[level + 1].second] = 0;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    for(int i = 1; i <= LENGTH; i++){
        for(int j = 1; j <= LENGTH; j++){
            cin >> sudoku[i][j];
            if(sudoku[i][j] == 0){
                zero.push_back(make_pair(i, j));
                zeroNum++;
            }
        }
    }

    bt(-1);
}

채점 결과