[C++/BackTracking/백준] 2580번 스도쿠

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

2580번: 스도쿠

---

백트래킹 문제 중 하나인 스도쿠 문제입니다. 9x9 격자가 주어졌을때 조건에 따라 빈칸을 다 채우는 것이 스도쿠 입니다.

조건은 다음과 같습니다.

 

1. 모든 칸에는 1~9사이의 숫자가 들어간다.

2. 행 9칸에는 1~9사이의 숫자가 중복되면 안된다.

3. 열 9칸도 마찬가지로 1~9사이의 숫자가 중복되면 안된다.

4. 3x3 격자로 나누게된다면 총 9개의 구역이 생기는데 빈칸을 채우려는 숫자의 구역에서도 1~9사이의 숫자간 겹치는 숫자가 발생하면 안된다.

 

0	3	5	4	6	9	2	7	8
7	8	2	1	0	5	6	0	9
0	6	0	2	7	8	1	3	5
3	2	1	0	4	6	8	9	7
8	0	4	9	1	3	5	0	6
5	9	6	8	2	0	4	1	3
9	1	7	6	5	2	0	8	0
6	0	3	7	0	1	9	5	2
2	5	8	3	9	4	7	6	0

스도쿠를 해결하는 로직은 다음과 같습니다.

먼저 빈칸에 숫자를 넣을때 조건에 맞춰서 숫자를 넣어보고, 다음 빈칸을 채워나가면서 조건이 맞지 않다면

1. 해당 빈칸의 숫자를 바꿔보거나

2. 이전 빈칸으로 백트래킹하여 숫자를 다시 바꾼뒤 다음 빈칸을 탐색하는 방법

두 가지 방법이 있습니다. 이 방법을 토대로 재귀 함수를 만들어줍니다.

 

void dfs(int level) //빈칸 level
{
    
    if(level==cnt)
    {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                cout<<map[i][j]<<" ";
            }
            cout<<'\n';
        }
        found = true;
        return;
    }
        
   
    int cur_y = v[level].first;
    int cur_x = v[level].second;
    for(int k=1;k<=9;k++) //재귀
    {
        map[cur_y][cur_x] = k;
        if(check(cur_y,cur_x)) //조건이 유효
        {
            
            dfs(level+1);
        }
        if(found)
        {
            return;
        }
        
    }
    map[cur_y][cur_x] = 0;
    return;
}

재귀 종료 변수인 level은 빈칸의 레벨 입니다. 다음 빈칸으로 넘어갈때 dfs(level+1)을 해주고 조건에 맞지 않다면 return 하여 재귀하여 돌아옵니다. 입력을 받을때 빈칸은 0으로 받기 때문에 map[i][j] == 0 일 경우에 v 배열에 push_back 하여 빈칸의 y와 x좌표를 저장해서 관리해줍니다.

 

check함수를 이용해 현재 y좌표와 x좌표를 매개 변수로 전달해 해당 빈칸의 숫자가 스도쿠 조건에 알맞는지 확인해줍니다. 알맞다면 다음 레벨로 재귀하고 맞지 않다면 해당 좌표를 0으로 다시 만들어 backTracking 해줍니다.

전체 소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>

using namespace std;

int map[9][9];
bool visited[9][9];

bool found = false;
vector<pair<int,int>>v; //비어있는 칸 모아놓은 배열
int level = 0; //비어있는 칸 순서대로 나열

int cnt = 0;

//1. 행체크
//2. 열체크
//3. 속한 9칸 체크
bool check(int y, int x)
{
    for(int i=0;i<9;i++) //행 체크 y만 바뀜 x고정
    {
        if(map[i][x]==map[y][x]&&i!=y)
        {
            return false;
        }
        if(map[y][i]==map[y][x]&&i!=x)
        {
            return false;
        }
            
    }

    int start_y = (y/3)*3;
    int start_x = (x/3)*3;
    for(int i=start_y;i<start_y+3;i++)
    {
        for(int j=start_x;j<start_x+3;j++)
        {   

            if((map[i][j]==map[y][x]))
            {
                if(i!=y&&j!=x)
                    return false;
            }
        }
    }
    return true;
}

void dfs(int level)
{
    
    if(level==cnt)
    {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                cout<<map[i][j]<<" ";
            }
            cout<<'\n';
        }
        found = true;
        return;
    }
        
   
    int cur_y = v[level].first;
    int cur_x = v[level].second;
    for(int k=1;k<=9;k++) //재귀
    {
        map[cur_y][cur_x] = k;
        if(check(cur_y,cur_x)) //조건이 유효
        {
            
            dfs(level+1);
        }
        if(found)
        {
            return;
        }
        
    }
    map[cur_y][cur_x] = 0;
    return;
}
int main()
{
    int num;
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<9;j++)
        {
            cin>>map[i][j];
            if(map[i][j]==0)
            {
                cnt++;
                v.push_back(make_pair(i,j));
            }
        }
    }

    dfs(level);

    
    return 0;
}