포스트

(백준/C++) 2580_스도쿠

백준 2580번: 스도쿠 (acmicpc.net) 문제는 백트래킹으로 해결할 수 있는 문제입니다.

문제를 차근차근 풀어나가고 정리해보면 어렵지 않은 문제지만, 접근법에 따라 잔실수가 많을 수 있는 문제입니다.

저 같은 경우는 기저사례로 해 찾기를 끝내려고 시도했다가 값이 초기화 되어 돌아가는 문제가 생기거나 Loop 종료 조건에서 고민을 하고, 이후 bool 조건으로 백트래킹을 빠져나오는 쪽으로 방향을 잡고 풀었습니다.

이 포스트를 보러 오셨다는 것은 문제 풀이 도중에 저처럼 막히거나 고민이 되는 부분이 있다고 생각하고, 이후 접근법이나 풀이 과정을 차근차근 설명 드리도록 하겠습니다.

접근법

우선, 스도쿠 문제의 접근법은 아래와 같습니다.

  1. 빈 칸을 찾습니다.
  2. 빈 칸에 1~9까지의 숫자를 넣고 같은 행, 같은 열, 같은 3X3 칸에 같은 숫자가 있는지 확인합니다.
  3. 모든 조건이 만족한다면 다음 빈 칸을 찾으러 넘어갑니다.
  4. 만약, 1~9까지의 모든 조건을 만족하지 않는다면, 다시 이전 칸으로 돌아가서 다른 수를 입력해 봅니다. (이 부분이 백트래킹이라고 생각됩니다.)
  5. 모든 칸을 채웠다면, 백트래킹을 종료합니다. (이때, 기록이 지워져서는 안됩니다. 따로 기록을 해두거나 백트래킹에 의해 기록이 변경된다면 종료시킬때 변경하지 않고 종료되도록 해야 합니다.)

스도쿠.webp


풀이 1

위 접근법으로 풀이를 풀었을 때, 제일 처음 설계한 방법은 2중 for문으로 빈 칸을 탐색하는 방법이었습니다.

이때, 숫자를 확인하고 for(1~9)의 모든 조건을 만족하지 않는다면, 빠져나와서 이전에 기록한 것을 0으로 만든 뒤 이어서 확인하는 과정이 필요합니다.

그 구분을 하기 위해 재귀 함수의 리턴 값으로 bool을 주고 실패한 경우에만 0으로 초기화 시키고 성공했다면 모든 기록이 완료된 것이므로 재귀함수를 순차적으로 빠져나오게 했습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
using namespace std;
int sudoku[9][9];

bool check(int x, int y, int n)
{
    //같은 행 또는 열에 같은 숫자가 있는지 확인
    for(int i = 0; i < 9; i++)
    {
        if (sudoku[x][i] == n || sudoku[i][y] == n)
            return false;
    }

    //3x3칸 안에 같은 숫자가 있는지 확인
    int startX = (x / 3) * 3;
    int 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;
}

bool write()
{
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            if (sudoku[i][j] == 0) //빈 칸 확인
            {
                for (int n = 1; n <= 9; n++) //1-9까지 숫자를 넣어보고
                {
                    if (check(i, j, n)) //확인한 뒤
                    {
                        sudoku[i][j] = n; //기록하고
                        if(write()) //다음으로 넘어간다.
                        {
                            return true; //스도쿠가 완성되면 true를 반환한다.
                        }
                        sudoku[i][j] = 0;
                    }
                }
                return false; //모든 수가 불가능하면 돌아가서 0으로 초기화 시킨다.
            }
        }
    }

    return true;
}

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

    for(int i = 0; i < 9; i++)
    {
        for(int j = 0; j < 9; j++)
        {
            cin >> sudoku[i][j];
        }
    }

    write();

    for (auto& row : sudoku)
    {
        for (auto& n : row)
            cout << n << ' ';
        cout << '\n';
    }
}

풀이 2

하지만, 위 방법에는 아쉬운 점이 있었습니다.

빈칸 확인을 처음부터 진행하기 때문에 빈칸을 놓치지 않겠지만, 백트래킹으로 빈칸을 채워나가기 때문에 빈칸부터 이어서 확인하게 하면 좋을 것 같습니다.

즉, 기존의 3중 for문으로 작동하던 부분을 좌표로 바꾸고 현재 좌표 이후로 탐색하도록 바꿨습니다.

이렇게 함으로써, 이미 확인한 칸을 다시 확인하는 것을 피할 수 있었습니다. (다만 속도의 차이는 유의미하게 크기는 않았습니다.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
using namespace std;
int sudoku[9][9];

bool check(int row, int col, int n)
{
    //같은 행 또는 열에 같은 숫자가 있는지 확인
    for (int i = 0; i < 9; i++)
    {
        if (sudoku[row][i] == n || sudoku[i][col] == n)
            return false;
    }

    //3x3칸 안에 같은 숫자가 있는지 확인
    int startX = (row / 3) * 3;
    int startY = (col / 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;
}

bool search(int row, int col)
{
    while (sudoku[row][col] != 0) //해당 칸이 비어있지 않았다면
    {
        if (++col >= 9) //다음 칸으로 넘어가는데, 한 행을 전부 탐색했다면 다음 행을 탐색한다.
        {
            col = 0;

            if (++row >= 9) //모든 칸을 탐색했다면 완료
                return true;
        }
    }

    for (int n = 1; n <= 9; n++) //1-9까지 숫자를 넣어보고
    {
        if (check(row, col, n)) //확인한 뒤
        {
            sudoku[row][col] = n; //기록하고

            if (search(row, (col + 1) % 9)) //다음으로 넘어간다.
                return true;    //이때, 기저사례를 통해 스도쿠가 완성되면 종료
        }
    }

    sudoku[row][col] = 0; //모든 숫자가 안된다면 초기화
    return false;
}

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

    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cin >> sudoku[i][j];
        }
    }

    search(0, 0);

    for (auto& row : sudoku)
    {
        for (auto& n : row)
            cout << n << ' ';
        cout << '\n';
    }
}
이 기사는 저작권자의 CC BY-NC-ND 4.0 라이센스를 따릅니다.