[백준] 2239_스도쿠 C++

06 Jul 2023 in Study on Coding Test

백트래킹을 활용해보는 구현 문제

정답제출코드

#include <iostream>
#include <string>
#include <cstring>

#define MAX 9

using namespace std;

int board[MAX][MAX];
bool row[MAX][10];
bool col[MAX][10];
bool square[MAX][10];

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

void backtrack(int cnt)
{
    int x = cnt / MAX;
    int y = cnt % MAX;

    if (cnt == 81)
    {
        print();
        exit(0);
    }

    if (board[x][y] == 0)
    {
        for (int i = 1; i <= 9; ++i)
        {
            if (!row[x][i] && !col[y][i] && !square[(x/3) * 3 + (y/3)][i])
            {
                row[x][i] = true;
                col[y][i] = true;
                square[(x/3) * 3 + (y/3)][i] = true;
                board[x][y] = i;
                backtrack(cnt+1);
                row[x][i] = false;
                col[y][i] = false;
                square[(x/3) * 3 + (y/3)][i] = false;
                board[x][y] = 0;
            }
        }
    }

    else
        backtrack(cnt+1);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    memset(row, false, sizeof(row));
    memset(col, false, sizeof(col));
    memset(square, false, sizeof(square));

    for (int i = 0; i < MAX; ++i)
    {
        string s;
        cin >> s;

        for (size_t j = 0; j < s.length(); ++j)
        {
            board[i][j] = s[j] - '0';
            if (board[i][j] != 0)
            {
                row[i][board[i][j]] = true;
                col[j][board[i][j]] = true;
                square[(i/3) * 3 + (j/3)][board[i][j]] = true;
            }
        }
    }

    backtrack(0);

    return 0;
}

참고링크를 참고해서 풀었다.

bool row[MAX][10];
bool col[MAX][10];
bool square[MAX][10];

의 의미부터 알아봐야 할 것 같았다.

스도쿠에는 행, 열, 사각형의 3가지 요소가 있으며,

몇 번째 행, 몇 번째 열, 몇 번째 사각형을 나타내는 인덱스가 0번부터 시작해서 9번까지 간다고 하면

row[i][j]의 의미는 i번째 행에서 숫자 j번은 사용되었다. 라는 의미가 될 것이다.

나머지 col, square의 의미도 같다.

즉, 아래 코드를 보면

for (size_t j = 0; j < s.length(); ++j)
{
    board[i][j] = s[j] - '0';
    if (board[i][j] != 0)
    {
        row[i][board[i][j]] = true;
        col[j][board[i][j]] = true;
        square[(i/3) * 3 + (j/3)][board[i][j]] = true;
    }
}

어떤 숫자를 true로 만들어주는 것은 이미 숫자가 들어가 있다는 의미이다.

백트래킹 코드에서도

if (!row[x][i] && !col[y][i] && !square[(x/3) * 3 + (y/3)][i])
{
    row[x][i] = true;
    col[y][i] = true;
    square[(x/3) * 3 + (y/3)][i] = true;
    board[x][y] = i;
    backtrack(cnt+1);
    row[x][i] = false;
    col[y][i] = false;
    square[(x/3) * 3 + (y/3)][i] = false;
    board[x][y] = 0;
}

행, 열, 사각형 모두에서 숫자가 사용되지 않아야 숫자를 넣을 수 있을테니 검사를 해주는 것이었다.

이 부분을 떠올리지 못해서 참고링크를 참고하였다.

이렇게 해서 왼쪽 위 사각형 부터 오른쪽 아래 사각형 까지 검사를 계속 해주어 백트래킹을 해준다.