[백준] 2239번 : 스도쿠 (C++)

2239번 : 스도쿠

---

문제)

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

 

 

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

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

 

 

입력 :

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

 

 

 

 

출력 :

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

 

 

 

 

 

 

 

풀이)

 

// 2239. 스도쿠
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
vector<vector<int>> vec(9);
bool flag = 1;
 
bool check(vector<vector<int>> &temp)
{
    int visited[10] = { 0 };
    int cnt = 0;
    for (int i = 0; i < 9; i++)
    {
        if (!visited[temp[0][i]])
        {
            visited[temp[0][i]] = 1;
            cnt++;
        }
    }
 
    if (cnt != 9) return false;
 
    for (int i = 0; i < 9; i++)
    {
        fill(&visited[0], &visited[10], 0);
        cnt = 0;
        for (int j = 0; j < 9; j++)
        {
            if (!visited[temp[j][i]])
            {
                visited[temp[j][i]] = 1;
                cnt++;
            }
        }
 
        if (cnt != 9) return false;
    }
    return true;
}
 
void print(vector<vector<int>> &temp)
{
    for (auto ele : temp)
    {
        for (auto e : ele)
        {
            cout << e;
        }
        cout << '\n';
    }
}
 
void recur(int row, int col, vector<vector<int>> &temp)
{
    // 첫번째 답이 나왔다면 다음 계산들은 모두 끝내버린다.
    if (!flag) return;
 
    // 마지막 종점에 다다랐을 때, (9, 9) 위치
    // 스도쿠가 완성되었는지 확인한다.
    if (row == 8 && col == 9)
    {
        if (check(temp) && flag)
        {
            print(temp);
            flag = 0;
        }
        return;
    }
 
    // 다음 행으로 넘겨준다.
    if (col == 9)
    {
        recur(row + 1, 0, temp);
    }
    else
    {
        // 해당 인덱스가 위치하는 열과, 행에서 해당 수가 없으면
        // 해당 수를 넣고 다음 인덱스로 넘어간다.
        if (temp[row][col] == 0)
        {
            int visited[10] = { 0 };
            for (int i = 0; i < 9; i++)
            {
                visited[temp[row][i]] = 1;
                visited[temp[i][col]] = 1;
            }
 
            int t_row = 0;
            int t_col = 0;
 
            if (0 <= row && row <= 2) t_row = 0;
            else if (3 <= row && row <= 5) t_row = 3;
            else if (6 <= row && row <= 8) t_row = 6;
 
            if (0 <= col && col <= 2) t_col = 0;
            else if (3 <= col && col <= 5) t_col = 3;
            else if (6 <= col && col <= 8) t_col = 6;
 
            for (int i = t_row; i < t_row + 3; i++)
            {
                for (int j = t_col; j < t_col + 3; j++)
                {
                    visited[temp[i][j]] = 1;
                }
            }
 
            for (int i = 1; i < 10; i++)
            {
                if (visited[i]) continue;
                temp[row][col] = i;
                recur(row, col + 1, temp);
                temp[row][col] = 0;
            }
        }
        else
        {
            recur(row, col + 1, temp);
        }
    }
}
 
int main()
{
    string temp;
 
    for (int i = 0; i < 9; i++)
    {
        cin >> temp;
        for (int j = 0; j < 9; j++)
        {
            vec[i].push_back(temp[j] - '0');
        }
    }
 
    recur(0, 0, vec);
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/2239 

2239번: 스도쿠