[백준] 2580 C++ 스도쿠문제 풀이(백트랙킹)

- 문제 설명

어렸을 때 자주 해봤던 스도쿠 퀴즈이다.

이 문제는 백트랙킹 기법을 사용해 쓸모없는 연산을 최소화 시키는게 관건이다.

그러기 위해서 순차적으로 다음과 같은 방식으로 동작해야한다.

 

- 문제 풀이

1. 9x9 크기의 배열을 만든다.

2. 빈 공간은 0으로 대체하기 때문에 값이 0인 곳들의 인덱스(x, y)를 저장할 배열을 추가로 만든다.

3. x, y를 저장한 배열을 처음부터 끝까지 돌면서 해당 좌표값에 1부터 9까지의 수를 넣으며 들어갈 수 있는 수라면 다음 좌표값을 진행하는 방식으로 동작한다.

4. 다음 좌표값에서 해를 찾지 못하면 그 전 좌표값에서 다른 해를 찾아본다.

5. 3,4 과정을 반복하며 모든 좌표값의 해를 찾았으면 진행중이 었던 백트랙킹을 중지시켜준다.

(들어오는 입력은 스도쿠 판을 규칙대로 채울 수 없는 경우는 없다고 가정한다.)

 

해를 만족하는 조건은 3가지를 고려하면 된다.

1. 가로줄에 같은 숫자가 없다면

2. 세로줄에 같은 숫자가 없다면

3. 스도쿠 판을 3x3으로 9개의 구역으로 나누었을때, 찾으려는 좌표 구역에 같은 숫자가 없다면

-> 3개의 조건을 모두 만족하는 숫자가 있다면 true 반대로 하나라도 만족하지 않는다면 false

이때 3x3으로 나눈 구역을 탐색하기 위해서는 n을 체크하려는 숫자라 한다면

(n / 3)*3 를 이용한 식을 쓰면 x, y의 범위를 구할 수 있다.

 

말로 설명하니 복잡한데 코드를 보면 더 이해가 쉽다.

 

 

- 코드

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

int board[9][9];
vector<pair<int, int>> coords;
bool found = false;
int cnt = 0; // 비어있는 갯수

void print()
{
    for(int i = 0; i < 9; i++)
        {
            for(int j = 0; j < 9; j++)
            {
                cout << board[i][j] << " ";
            }
            cout << '\n';
        }
}

bool check(pair<int, int> p)
{
    for(int i = 0; i < 9; i++)
    {
        if(board[i][p.second] == board[p.first][p.second] && i != p.first)
            return false; // 세로줄 중에 같은 수가 있다면 (자신 제외)
        if(board[p.first][i] == board[p.first][p.second] && i != p.second)
            return false; // 가로줄 중에 같은 수가 있다면 (자신 제외)
    }
    for(int i = (p.first/3)*3; i < (p.first/3)*3 + 3; i++)
        for(int j = (p.second/3)*3; j < (p.second/3)*3 + 3; j++)
        {
            if(board[i][j] == board[p.first][p.second])
            {   // 자신이 속해있는 구역 안에 같은 수가 있다면
                if(i != p.first && j != p.second) // 자신 제외
                    return false;
            }
        }
        
    return true;
}

void sudoku(int depth)
{
    if(depth == cnt) // 해를 모두 찾아 냈다면 
    {
        print();
        found = true; // 백트랙킹을 중지 시키기 위해 
        return;
    }
    
    for(int i = 1; i <= 9; i++)
    {
        board[coords[depth].first][coords[depth].second] = i; // 1부터 9까지 숫자를 넣어보며 해 찾기
        if(check(coords[depth]))
            sudoku(depth+1); // 해를 찾으면 다음 좌표의 해 탐색
        if(found) // 해를 모두 찾았으면 더 이상의 연산을 피하기 위해 
            return;
    }
    board[coords[depth].first][coords[depth].second] = 0; // 백트랙킹 중 해를 찾지 못했을 경우 원래대로 돌려놔야 함  
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    for(int i = 0; i < 9; i++)
        for(int j = 0; j < 9; j++)
        {
            cin >> board[i][j];
            if(board[i][j] == 0)
            {
                cnt++;
                coords.push_back({i, j});
            }
        }
    
    sudoku(0);
    
    
    return 0;
}