[백준 C++] 2239번 스도쿠

2239번: 스도쿠

문제 요약

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

사용 알고리즘

DFS

입출력

• 입력: 9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.
• 출력: 9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다. ``` 예제1

입력 103000509 002109400 000704000 300502006 060000050 700803004 000401000 009205800 804000107 출력 143628579 572139468 986754231 391542786 468917352 725863914 237481695 619275843 854396127

## 풀이
DFS를 이용하여 푸는 문제이다. 빈칸에 하나씩 숫자를 넣어보다가 안되는경우 돌아가서 다음숫자를 넣어보는 식으로 풀면 된다. 

## 어려웠던 점
숫자를 넣었을때 스도쿠가 오류가 나지 않는지 가로, 세로, 3*3칸을 확인하는 코드가 생각보다 어려웠다. i와 j의 위치를 잘 생각해야한다.

## 배운 점 / 느낀 점
이코드를 짜고 스도쿠 사이트에 들어가 가장 어려운 걸로 풀었는데 바로 맞았다. 완전탐색이니 난이도에 상관없이 모두 풀 수 있다. 

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <cstdlib>
using namespace std;

vector<unordered_set<int>> row;
vector<unordered_set<int>> column;
vector<unordered_set<int>> square;
vector<pair<int,int>> blank;
vector<vector<int>> m_row;

bool isgood(int i, int j, int data){
    return row[i].count(data) == 0 && column[j].count(data) == 0 && square[(i/3)*3+j/3].count(data) == 0;
}

void dfs(int index){
    if(index == blank.size()){
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                cout << m_row[i][j];
            }
        cout << '\n';
        }
        exit(0);
    }
    int x = blank[index].second;
    int y = blank[index].first;
    for (int i = 1; i <= 9; i++) {
        if(isgood(y,x,i)){
            row[y].insert(i);
            m_row[y][x] = i;
            column[x].insert(i);
            square[(y/3)*3+x/3].insert(i);
            dfs(index+1);
            row[y].erase(i);
            m_row[y][x] = 0;
            column[x].erase(i);
            square[(y/3)*3+x/3].erase(i);
        }
    }
}

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

    string s;

    row = vector<unordered_set<int>>(9, unordered_set<int>());
    column = vector<unordered_set<int>>(9, unordered_set<int>());
    square = vector<unordered_set<int>>(9, unordered_set<int>());
    m_row = vector<vector<int>>(9, vector<int>(9,0));
    blank = vector<pair<int,int>>();

    for (int i = 0; i < 9; i++) {
        cin >> s;
        for (int j = 0; j < 9; j++) {
            m_row[i][j] = (s[j]-'0');
            if(s[j] == '0'){
                blank.push_back({i,j});
                continue;
            }
            row[i].insert(s[j]-'0');
            column[j].insert(s[j]-'0');
            square[(i/3)*3+j/3].insert(s[j]-'0');
        }
    }
    dfs(0);


    

    return 0;
}