백준 2239번 스도쿠

🔒[문제 url]

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

🔑알고리즘

가능한 답안 중 사전 기준 앞에 오는 답안을 출력해야하므로,
앞에서부터 작은 수를 채워나간다.

• 칸에 수를 채울때 따져야하는 조건은 다음과같이 세 가지이다.

1. 해당 칸이 속한 행에 채우고자하는 수가 없어야한다.
2. 해당 칸이 속한 열에 채우고자하는 수가 없어야한다.
3. 해당 칸이 속한 $3\times3$의 구역에 채우고자하는 수가 없어야한다.
   
   

• 채울 수가 없는 칸의 경우, 이전 칸으로 돌아가 다른 수를 채운 후 다시 따져본다. BackTracking
  이전 칸으로 돌아갈때, 현재 칸은 0으로 갱신해야함에 주의한다.

🐾부분 코드

bool checkHorizontal(int row, int n)
{
    for (int i = 0; i < 9; i++)
        if (sudoku[row][i] == n) return false;
    return true;
}

<해당 칸이 속한 행 탐색>
채우고자하는 수n이 속해있다면 false를, 아니면 true를 반환한다.

bool checkVertical(int col, int n)
{
    for (int i = 0; i < 9; i++)
        if (sudoku[i][col] == n) return false;
    return true;
}

<해당 칸이 속한 열 탐색>
채우고자하는 수n이 속해있다면 false를, 아니면 true를 반환한다.

bool checkArea(int x, int y, int n)
{
    int startX = (x / 3) * 3, startY = (y / 3) * 3;
    for (int i = startX; i < startX + 3; i++)
        for (int j = startY; j < startY + 3; j++)
            if (sudoku[i][j] == n)
                return false;
    return true;
}

<해당 칸이 속한 구역 탐색>
채우고자하는 수n이 속해있다면 false를, 아니면 true를 반환한다.
해당 칸이 속한 구역을 구분하기 위해, 구역의 가장 왼쪽 위에 해당하는 칸을 수식을 통해 구한다.

int startX = (x / 3) * 3, startY = (y / 3) * 3;

이후 위 좌표를 시작으로 $3 \times3$ 크기만큼 탐색한다.

🪄전체 코드

#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> pii;
int sudoku[9][9];
vector<pii> zero;

void INPUT()
{
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
        {
            scanf("%1d", &sudoku[i][j]);
            if (!sudoku[i][j]) zero.push_back({i, j});
        }
}

bool checkHorizontal(int row, int n)
{
    for (int i = 0; i < 9; i++)
        if (sudoku[row][i] == n) return false;
    return true;
}

bool checkVertical(int col, int n)
{
    for (int i = 0; i < 9; i++)
        if (sudoku[i][col] == n) return false;
    return true;
}

bool checkArea(int x, int y, int n)
{
    int startX = (x / 3) * 3, startY = (y / 3) * 3;
    for (int i = startX; i < startX + 3; i++)
        for (int j = startY; j < startY + 3; j++)
            if (sudoku[i][j] == n)
                return false;
    return true;
}

void SOLVE()
{
    /*
     * 앞에서부터 작은 수를 채우되,
     * 들어갈 수 있는 수가 없는 칸을 만나면 이전 칸으로 돌아와 다시 채우기를 반복
     */
    int vSize = zero.size();
    for (int i = 0; i < vSize; i++)
    {

        int x = zero[i].first, y = zero[i].second;
        // If Empty position

        // find the min num that can fill the position
        bool filled = false;
        for (int num = sudoku[x][y] + 1; num <= 9; num++)
        {
            // Check three condition
            if (checkHorizontal(x, num)
                && checkVertical(y, num)
                && checkArea(x, y, num))
            {
                sudoku[x][y] = num;
                filled = true;
                break;
            }
        }

        // No num to fill in, back to previous position
        if (!filled)
        {
            sudoku[x][y] = 0;
            i -= 2;
        }

    }//for i end

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

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

태어나서 푼 스도쿠만 3000문제는 거뜬히 넘을 나 자신..풀수밖에 없겠군!!
오랜만에 만난 백트래킹 문제였는데 헤매지않고 금방 해결해 기분이 좋았다.
하긴 솔브닥 GOLD1 달고 GOLD4를 헤매면 안 되지..
뭐! 다른 문제는 헤맬수도 있지!