(백준/C++) 2580_스도쿠
백준 2580번: 스도쿠 (acmicpc.net) 문제는 백트래킹으로 해결할 수 있는 문제입니다.
문제를 차근차근 풀어나가고 정리해보면 어렵지 않은 문제지만, 접근법에 따라 잔실수가 많을 수 있는 문제입니다.
저 같은 경우는 기저사례로 해 찾기를 끝내려고 시도했다가 값이 초기화 되어 돌아가는 문제가 생기거나 Loop 종료 조건에서 고민을 하고, 이후 bool 조건으로 백트래킹을 빠져나오는 쪽으로 방향을 잡고 풀었습니다.
이 포스트를 보러 오셨다는 것은 문제 풀이 도중에 저처럼 막히거나 고민이 되는 부분이 있다고 생각하고, 이후 접근법이나 풀이 과정을 차근차근 설명 드리도록 하겠습니다.
접근법
우선, 스도쿠 문제의 접근법은 아래와 같습니다.
- 빈 칸을 찾습니다.
- 빈 칸에 1~9까지의 숫자를 넣고 같은 행, 같은 열, 같은 3X3 칸에 같은 숫자가 있는지 확인합니다.
- 모든 조건이 만족한다면 다음 빈 칸을 찾으러 넘어갑니다.
- 만약, 1~9까지의 모든 조건을 만족하지 않는다면, 다시 이전 칸으로 돌아가서 다른 수를 입력해 봅니다. (이 부분이 백트래킹이라고 생각됩니다.)
- 모든 칸을 채웠다면, 백트래킹을 종료합니다. (이때, 기록이 지워져서는 안됩니다. 따로 기록을 해두거나 백트래킹에 의해 기록이 변경된다면 종료시킬때 변경하지 않고 종료되도록 해야 합니다.)
풀이 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';
}
}