백준 2580번 : 스도쿠

• 분류: 백트래킹

코드

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

int table[9][9];
bool flag = false;

vector<int> find_candidate(int i, int j) {
    bool nums[9] = {false,};
    for(int x=0 ; x<9 ; x++) {
        if(table[x][j]!=0) nums[table[x][j]-1]=true;
    }
    for(int x=0 ; x<9 ; x++) {
        if(table[i][x]!=0) nums[table[i][x]-1]=true;
    }
    for(int x=3*(i/3) ; x<3*(i/3)+3 ; x++) {
        for(int y=3*(j/3) ; y<3*(j/3)+3 ; y++) {
            if(table[x][y]!=0) nums[table[x][y]-1]=true;
        }
    }
    vector<int> result;
    result.clear();
    for(int x=0 ; x<9 ; x++) if(!nums[x]) result.push_back(x+1);
    return result;
}

void backtrack() {
    for(int i=0 ; i<9 ; i++) {
        for(int j=0 ; j<9 ; j++) {
            if(table[i][j]==0) {
                vector<int> candidates = find_candidate(i, j);
                for(int c : candidates) {
                    table[i][j] = c;
                    backtrack();
                    if(flag) return;
                }
                table[i][j]=0;
                return;
            }
        }
    }
    flag = true;
}


int main() {
    for(int i=0 ; i<9 ; i++) {
        for(int j=0 ; j<9 ; j++) {
            cin >> table[i][j];
        }
    }
    backtrack();

    for(int i=0 ; i<9 ; i++) {
        for(int j=0 ; j<8 ; j++) {
            cout << table[i][j] << ' ';
        }
        cout << table[i][8] << '\n';
    }
}

• 코멘트
  
  백트래킹으로 풀 수 있는 전형적인 문제이다.
  재귀함수 하나를 이용해서 가능한 수를 채워널어가면서 숫자를 더 넣지 못하면 되돌아가고, 끝까지 채웠으면 결과를 출력하면 된다.
  vector<int> find_candidate(int i, int j)는 (i, j) 좌표에 넣을 수 있는 숫자들을 벡터에 넣어서 반환하는 함수이다. 상하, 좌우, 3x3q 박스를 살펴본다.
  이 candidates에 있는 후보들을 하나씩 table에 채워 넣고 재귀의 다음 depth로 보내본다. 만약 재귀가 도착점에 도달하지 못하고 return해서 돌아왔다면 그것은 실패한 경우의 수가 된다.
  모든 candidate를 다 보내봤는데 전부 도착점에 도달하지 못하고 return해왔으면 이전 단계부터 글러먹은 것이니 table[i][j]를 초기화한 후 return한다.
  

• 헤맨 부분
  bool nums[9] = {false,}; 에서 배열이 자동 초기화되는 줄 알고 bool nums[9];로 했다가 한참 틀렸다. undefined behavior가 나타나게 되는 것 같다.