스도쿠 2239

문제

접근 방법

백트래킹으로 해결해 줄 수 있다.
9개의 선택지가 9^2만큼 있으니 9^81일 것이다.
하지만 같은 줄, 같은 영역에 존재하는 경우를 제외해 주면서 해결해 주면 시간은 줄어들 것이다.

코드

#include <iostream>
#include <string>
using namespace std;
int map[9][9];
bool isExist[2][9][10];       // (가로, 세로) 여부, 몇 번째 줄, 어느 값
bool isSquareExist[3][3][10]; // 영역, 어느 값
void dfs(int index)
{
    if (index == 81)
    {
        for (int i = 0; i < 9; ++i)
        {
            for (int j = 0; j < 9; ++j)
                cout << map[i][j];
            cout << "\n";
        }
        exit(0);
    }
    int y = index / 9;
    int x = index % 9;
    if (map[y][x])
        dfs(index + 1);
    else
        for (int i = 1; i <= 9; ++i)
        {
            if (isExist[0][y][i] || isExist[1][x][i] || isSquareExist[y / 3][x / 3][i])
                continue;
            isExist[0][y][i] = isExist[1][x][i] = isSquareExist[y / 3][x / 3][i] = true;
            map[y][x] = i;
            dfs(index + 1);
            map[y][x] = 0;
            isExist[0][y][i] = isExist[1][x][i] = isSquareExist[y / 3][x / 3][i] = false;
        }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    string input;
    for (int i = 0; i < 9; ++i)
    {
        cin >> input;
        for (int j = 0; j < 9; ++j)
        {
            map[i][j] = input[j] - '0';
            isExist[0][i][map[i][j]] = isExist[1][j][map[i][j]] = isSquareExist[i / 3][j / 3][map[i][j]] = true;
        }
    }
    dfs(0);
    return 0;
}

풀이

처음에는 문제를 대충 보고 같은 영역은 확인 안 했다.
영역은 y와 x를 3으로 나누었을 때 9개의 칸으로 나뉜다는 점을 활용하여 방문 처리해 주면 된다.
가로와 세로는 각각 가로의 경우, 세로의 경우를 나누어서 해당하는 값이 사용됐는지 확인해 주면 된다.