[BOJ][백트래킹][골4][2239] 스도쿠

문제 링크

문제 링크

풀이

알고리즘

2차원 N자리 K진수를 적용해서 해결하는 문제입니다. 선택한다/안한다의 방법을 적용합니다.

[이론][완전탐색][N자리 K진수] Chapter 4를 확인해보세요.

종료조건을 x,y 좌표가 벗어났을 때로 설정합니다. 그리고 check()에서 가로/세로/3*3 중 하나라도 불가능하면 더이상 진행하지 않도록 합니다. 이때 0은 중복 확인에서 제외합니다.

check()를 할 때 현재 x,y 좌표를 기준으로 가로 9개, 세로 9개, 3 * 3 개(현재 x,y가 속한 영역)을 모두 확인해야 합니다.(값이 0인 경우 제외) (0,0)부터 (x,y)까지만 확인한다면 불필요한 재귀를 반복하게 됩니다.

예를 들어 (0,1)자리의 숫자를 9로 설정하고 recur()를 진행하는 경우 가로 9개 테스트에서 불가능함을 미리 파악할 수 있게 됩니다.

193000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

1. 소문난 칠공주 문제의 경우 선택하는 횟수(cnt)로 종료 조건 만들었다면, 스도쿠는 x,y좌표로만 가지고 종료 조건 설정하기
2. 특정 좌표의 값이 0이 아닌 경우 바로 recur(x,y+1)
3. 특정 좌표의 값이 0인 경우 for()문 순회
4. 특정 좌표의 값을 채우고, correct()를 통해서 가로 9개, 세로 9개, 3*3 9개 칸만 확인해서 불필요한 recur() 없애기
5. recur()타고 쭉쭉 들어갔는데 특정 좌표에서 1~9 모두 들어가지 못하는 경우 원래 0이었던 칸을 다시 0으로 만들면서 back-tracking 진행하기
6. 최초의 정답 출력 후 모든 recur() 무마시키기
7. check() 호출 중 임의의 위치에서 return false 되었다가 다시 check()호출될 때도 memset(visited)되도록 memset 위치 설정하기

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int arr[9][9];
bool visited[10]; // visited[i] : 값 i를 사용한 적이 있는가?

bool check(int x, int y) {
    if (x == 0 && y == 0) return true;
    int curr = 0;
    // 가로 테스트
    memset(visited, false, sizeof(visited));
    for (int i = 0; i < 9; i++) {
        curr = arr[x][i];
        if (curr && visited[curr]) return false;
        visited[curr] = true;
    }
    // 세로 테스트
    memset(visited, false, sizeof(visited));
    for (int i = 0; i < 9; i++) {
        curr = arr[i][y];
        if (curr && visited[curr]) return false;
        visited[curr] = true;
    }
    // 3 * 3 테스트. 매번 (x,y)가 포함된 3 * 3에서 0이 아닌 중복을 찾는다
    memset(visited, false, sizeof(visited));
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            curr = arr[x / 3 * 3 + i][y / 3 * 3 + j];
            if (curr && visited[curr]) return false;
            visited[curr] = true;
        }
    }
    return true;
}

bool flag = false;
void recur(int x, int y) {
    if (flag) return;

    // 2차원 N자리 K 진수
    if (y == 9) {
        x++;
        y = 0;
    }

    // 종료 조건
    if (x == 9) {
        flag = true;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                cout << arr[i][j];
            }
            cout << "\n";
        }
        return;
    }
    if (arr[x][y]) {
        recur(x, y + 1);
    }
    else
    {
        for (int i = 1; i <= 9; i++) {
            arr[x][y] = i;
            if (check(x, y)) recur(x, y + 1);
        }
        /*
        (x,y)에 1~9 중 어떤 값도 올 수 없다면
        현재 recur()를 호출하기 이전의 recur()에서
        잘못된 수를 선택한 경우입니다.
        값을 0으로 되돌려 놓아야 이전 recur()의 값을 바꾸었을 때
        다시 1~9을 넣어서 테스트할 수 있습니다.
        */
        arr[x][y] = 0;
    }
}

int main()
{
    freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            scanf("%1d", &arr[i][j]);
        }
    }
    recur(0, 0);

    return 0;
}

Success Notice: 2 차원 N 자리 K진수 개념을 사용한 문제를 풀어봤습니다. 수고하셨습니다.