백준 2580 스도쿠

작성일 | In |

Problem : 스도쿠

유형 : 백트래킹

문제 설명

스도쿠

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다. 모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다. 스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

스도쿠 완성

예제 입력

1
2
3
4
5
6
7
8
9
0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0

예제 출력

1
2
3
4
5
6
7
8
9
1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1

해결 전략

복잡해 보이지만, 기능별로 함수를 나누면 된다.
해당 열과 행에 숫자가 사용되고 있는지를 구별하고
동시에 어느 위치의 박스에 숫자가 사용되고 있는지를 확인한다.
여기서 박스의 위치란 다음과 같다.

0 1 2
3 4 5
6 7 8

0번 박스는 3행 이하이고, 3열 이하이다.
1번 박스는 3행 이하이고 6열 이하이다.
3번 박스는 3행 이상 6행 이하이고 3열 이하이다.

box_num = (nx/3) * 3 + (ny/3); 행과 열은 0부터 시작

숫자를 넣었을 때 사용하지 못하면, 다음 숫자를 찾고
모든 숫자를 시도했을 때에도 답이 안되면
이전에 채운 공백의 숫자를 바꾸어본다.

주의할 점

  • 해당 위치에 1부터 9까지 모든 숫자가 들어가는것이 불가능할때
  • 이전에 좌표에 들어간 숫자가 잘못된 숫자란 이야기 이므로
  • 해당 위치를 스택에 넣고, 이전 좌표의 숫자를 변경시켜야한다.

풀이

초기 상태의 스도쿠를 입력받는다.

  • 빈공간의 좌표는 따로 스택에 넣어서 관리한다.
  • 숫자인 경우 해당 좌표의 열, 행, 박스에 숫자가 있음을 표시해둔다.
    • row[5][1] = 5번 행에 1번이 존재한다.

공백 이었던 곳에 숫자를 하나씩 넣어본다.

  • 공백에 숫자를 채우기 전 해당 숫자가 해당 열, 행, 박스에 사용중인지 확인한다.
  • 숫자를 채운 경우 표시를 해둔다.
  • 다음 빈공간을 찾으러 간다.
    • 스택이 비었다면, 스도쿠를 완성 했으므로 답을 출력한다.

코드

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
#define pp pair<int, int>
using namespace std;

int n = 9;
int board[10][10];

bool row[10][11];
bool col[10][11];
bool box[10][11];

bool find_answer;

stack<pair<int, int> > STACK;

int find_box_num(int nx, int ny) {
	int box_num = (nx/3) * 3 + (ny/3);
	return box_num;
}

bool box_check(int nx, int ny, int idx) {
	int box_num = find_box_num(nx, ny);
	return box[box_num][idx];
}

void box_set(int nx, int ny, int value, bool b) {
	int box_num = find_box_num(nx, ny);
	box[box_num][value] = b;
}

void output() {
	for (int i = 0; i < n; ++i) {
		for (int ii = 0; ii < n; ++ii) {
			cout << board[i][ii] << " ";
		}
		cout << "\n";
	}
}

void dfs() {
	if (find_answer)return;

	if (STACK.empty()) {
		output();
		find_answer = true;
		return;
	}

	pp cur = STACK.top();	STACK.pop();

	int nx = cur.first;
	int ny = cur.second;

	for (int i = 1; i <= 9; ++i) {
		if (row[nx][i])continue;
		if (col[ny][i])continue;
		if (box_check(nx, ny, i))continue;

		row[nx][i] = true;
		col[ny][i] = true;
		box_set(nx, ny, i, true);
		board[nx][ny] = i;

		dfs();

		row[nx][i] = false;
		col[ny][i] = false;
		box_set(nx, ny, i, false);
		board[nx][ny] = 0;
	}
	STACK.push(cur);
}

void solve() {
	dfs();
}

void input() {
	int value;
	for (int i = 0; i < n; ++i) {
		for (int ii = 0; ii < n; ++ii) {
			cin >> value;
			board[i][ii] = value;

			if (value == 0) STACK.push({ i,ii });
			else {
				row[i][value] = true;
				col[ii][value] = true;
				box_set(i, ii, value, true);
			}
		}
	}
}

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

	freopen("input.txt", "r", stdin);
	input();
	solve();

	return 0;
}

피드백

2020-03-03 기준 지금 보니까 소스가 개판이다.
비슷한문제를 그냥 뜯어 고쳐서 다시 풀어야겠다.