[BOJ / C++] 2580 스도쿠

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

문제풀이

1. 입력을 받을 때 비어있는 칸의 좌표를 blank 벡터에 다 넣어놓는다. (vetor<pair<int,int>> blank)
2. blank 인덱스 0부터~ blank size까지 레벨을 뻗으면서 스도쿠를 완성시켜주며 dfs를 진행한다.
3. 따라서 blank size까지 레벨이 뻗었을 때 스도쿠가 완성되고, 이때 여러개의 답이 있을 때 하나만 출력해주면 되므로 exit(0)을 사용했다.
   3.dfs 내에서는 int candidate[10] 배열을 이용해 가로, 세로, 9칸을 검사한 후 이미 존재하는 번호는 candidate[존재하는 번호]=1 로 만들어주었다.
4. 따라서 candidate 배열을 1~9 인덱스까지 돌면서 candidate[i]==0 일 때, 현재level(=black 인덱스) 의 r,c 좌표에 해당 번호를 넣고(map[r][c]=i) 다음 레벨로 재귀를 실행한다.
   당연히 백트래킹 한 후엔 map[r][c]=0으로 되돌려야함!

코드

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

int map[10][10];
vector<pair<int,int>> blank;
void sudoku(int level){
    // 스도쿠 완성
    if(level==blank.size()){
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                cout<<map[i][j]<<" ";
            }
            cout<<"\n";
        }
        exit(0); //여러 개일 경우, 처음 완성 된 한 번만 출력!
    }

    int r=blank[level].first;
    int c=blank[level].second;

    int candidate[10]={0,};

    //가로, 세로
    for(int i=0;i<9;i++){
        if(map[r][i]) candidate[map[r][i]]=1;
        if(map[i][c]) candidate[map[i][c]]=1;
    }

    //9칸.
    int restR=r%3;
    int restC=c%3;
    for(int i=r-restR;i<r-restR+3;i++){
        for(int j=c-restC;j<c-restC+3;j++){
            if(map[i][j]) {
                candidate[map[i][j]]=1;
            }
        }
    }

    //후보!
    for(int i=1;i<=9;i++){
        if(candidate[i]==0){
            map[r][c]=i;
            sudoku(level+1);
            map[r][c]=0; //백트래킹. //레벨까지 못 갈 수도 있기 때문에 여러 경로
        }
    }
}

int main(){
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            cin>>map[i][j];
            if(map[i][j]==0){
                blank.push_back({i,j});
            }
        }
    }
    sudoku(0);
}