[C++] 백준 2580번: 스도쿠

🔗 문제

2580번: 스도쿠

2580번: 스도쿠

 

🖍 풀이

스도쿠 칸에 값을 넣는 조건

• 가로와 세로에 중복된 숫자가 올 수 없다.
• 3*3짜리 9칸으로 나눴을 때 영역에 중복된 숫자가 올 수 없다.

이 조건을 잘 생각해서 완전 탐색을 해보자.

 

입력

빈칸 탐색하기 싫어서 입력을 받을 때 빈칸인 좌표를 zeros에 저장해주었다.

 

완전 탐색

for(int i=1; i<=9; ++i)
{
    int x = zeros[idx].first;
    int y = zeros[idx].second;

    //영역 중복과 가로 세로 중복 확인
    if(check_area(x, y, i) && check_direction(x, y, i))
    {
        sudoku[x][y] = i;
        solve(idx+1);
        sudoku[x][y] = 0;
    }
}

• 빈 칸에다가 1부터 9까지 다 때려넣어서 조건이 맞다면 다음 빈칸을 채우도록 함수를 만들었다.
• 빈 칸을 하나씩 채울 때마다 idx가 증가한다.

 

출력

이 문제는 다 풀었을 때 모든 경우의 수를 보고 싶은게 아니기 때문에 빈칸이 다 채워지면 바로 함수를 종료하기 위해 exit(0)로 프로그램 종료해준다.

void solve(int idx)
{
    if(idx == zeros.size()) // 빈칸 다 채웠다.
    {
        for(const auto& arr : sudoku)
        {
            for(const auto& i : arr)
                std::cout << i << ' ';
            std::cout << '\\n';
        }
        exit(0); // return 이 아니라 출력하고 프로그램 종료!! 
    }
    
    //...
}

 

💾  소스

#include <iostream>
#include <vector>
#include <queue>

int sudoku[9][9];
std::vector<std::pair<int, int>> zeros;

bool check_area(int r, int c, int num)
{
    int x = r/3; int y =c/3;

    for(int i=x*3; i<(x*3) + 3; ++i)
    {
        for(int j=y*3; j<(y*3) + 3; ++j)
        {
            if(sudoku[i][j] == num)
                return false;
        }
    }
        
    return true;
}

bool check_direction(int r, int c, int num)
{
    for(int i=0; i<9; ++i)
    {
        if(sudoku[r][i] == num)
            return false;
        if(sudoku[i][c] == num)
            return false;
    }
    
    return true;
}

void solve(int idx)
{
    if(idx == zeros.size())
    {
        //output
        for(const auto& arr : sudoku)
        {
            for(const auto& i : arr)
                std::cout << i << ' ';
            std::cout << '\\n';
        }
        exit(0);
        
        return;
    }
    
    for(int i=1; i<=9; ++i)
    {
        int x = zeros[idx].first;
        int y = zeros[idx].second;
        
        if(check_area(x, y, i) && check_direction(x, y, i))
        {
            sudoku[x][y] = i;
            solve(idx+1);
            sudoku[x][y] = 0;
        }
    }
    
    return;
}

int main()
{
    for(int i=0; i<9; ++i)
    {
        for(int j=0; j<9; ++j)
        {
            std::cin >> sudoku[i][j];
            if(sudoku[i][j] == 0)
            {
                zeros.push_back({i, j});
            }
        }
    }
    
    solve(0);
    
    return 0;
}