[알고리즘] 백준 2580번: 스도쿠 (C++), exit(0); 백트래킹 보완

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

이번 문제는 공부할 포인트가 많았다.

글과 코드가 꽤 길기 때문에 앞서 공부할 내용을 정리하면

• 배열의 역할, 발상의 전환
• exit(0); -> 프로그램 자체 종료
• DFS에서 다음 좌표값도 넘겨주기 (시간 소요 줄임)

처음엔 백트래킹을 생각하지 않고 풀려했다.

스도쿠 표를 1행 1열부터 탐색하면서 0이면 check함수를 콜 하여 그 자리에 들어올 수를 넣어주었다.

허나, 아래 코드를 보면 이 방법이 잘못되었다.

어떤 좌표로부터 가로와 세로, 그리고 블록까지 탐색하여 들어갈 수 있는 제일 작은 수를 넣어준 게 발상의 잘못된 점이었다.

#include <iostream>
using namespace std;

int map[10][10];
bool visited[10];

void bt1(int r) {
	// 가로 검사
	for (int i = 1; i <= 9; i++) {
		if (!visited[map[r][i]] && map[r][i] != 0) {
			visited[map[r][i]] = 1;
		}
	}
}

void bt2(int c) {
	// 세로 검사
	for (int i = 1; i <= 9; i++) {
		if (!visited[map[i][c]] && map[i][c] != 0) {
			visited[map[i][c]] = 1;
		}
	}
}

void bt3(int r, int c) {
	// 블럭 검사
	int rlimit = (r - 1) / 3;
	int climit = (c - 1) / 3;

	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			if ((i - 1) / 3 == rlimit && (j - 1) / 3 == climit) {
				if (!visited[map[i][j]] && map[i][j] != 0) {
					visited[map[i][j]] = 1;
				}
			}
		}
	}
}

int check(int row, int col) {
	bt1(row);
	bt2(col);
	bt3(row, col);

	for (int i = 1; i <= 9; i++) {
		if (!visited[i]) {
			return i;
		}
	}
	return 0;
	// return 0; 안 달아주면 마지막에 i++된 10이 리턴 됨
}

int main() {
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			if (map[i][j] == 0) {
				for (int k = 1; k <= 9; k++) {
					visited[k] = 0;
				}
				map[i][j] = check(i, j);
			}
		}
	}

	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			cout << map[i][j] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

이럴 경우 다음 TC에서 정답이 아니라고 뜬다.

[Input]
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

[Answer]
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 2 9 7 8
6 4 2 9 7 8 5 3 1
9 7 8 5 3 1 6 4 2

[Output]
1 2 3 4 5 6 7 8 9
4 5 6 1 2 3 0 0 0
7 8 9 0 0 0 1 2 3
2 1 4 3 6 5 8 7 0
3 6 5 2 1 4 9 0 0
8 7 0 9 0 0 2 1 4
5 3 1 6 4 2 0 9 7
6 4 2 5 3 1 0 0 8
9 0 7 8 0 0 3 4 1

Output에서 0이 출력되는 부분들이 뜻하는 바는 '들어올 수 있는 수가 없다.'이다.

즉, 제일 작은 수를 넣을 게 아니라 한 번 넣은 수, 그다음의 수가 들어올 수 있는 수가 없다면

한 번 넣은 수를 바꿔서 넣어줄 필요가 있다는 뜻이다.

>> 간단하게 설명하면 예를 들어 어딘가에 1을 넣었다고 하자 그런데 그다음의 수가 들어올 수 있는 수가 없다면 직전에 넣었던 수 1이 아닌 다른 수를 넣어서 다음 수를 고려해봐야 한다는 뜻이다.

>> 이 과정에서 백트래킹을 떠올릴 수 있다.

---

[솔루션]

(참고: https://yabmoons.tistory.com/88)

그렇다면 어떻게 백트래킹을 하는가?

❓[1번째 포인트]

입력을 받을 때, 0이 아닌 수가 들어온다면 해당 행의 위치, 열의 위치, 블록의 위치에 해당하는 수가 있다고 체크해준다.

이 부분은 전에 포스팅했던 발상의 전환과 비슷하다고 느꼈다.

 

꼭 배열의 행이나 열이 좌표를 가리키거나 숫자를 카르길 필요는 없다는 발상.

https://draw-code-boy.tistory.com/117

[알고리즘] 2차원 배열이란 키워드

for (int i = 1; i <= 9; i++) {
	for (int j = 1; j <= 9; j++) {
		cin >> map[i][j];
		if {
			row[i][map[i][j]] = true;
			col[j][map[i][j]] = true;
			block[checkBlock(i, j)][map[i][j]] = true;
		}
	}
}

블록 별로 숫자를 매기는 함수는 굳이 설명을 하지 않아도 될 거 같다.

int checkBlock(int r, int c) {
	int y = ((r - 1) / 3);
	int x = ((c - 1) / 3) + 1;

	return y * 3 + x;
}

 

그다음 내가 짰던 백트래킹을 먼저 보여주고 나서 왜 시간 초과가 났었는지 설명하겠다.

우선, 이 함수에 있는 zeroCnt는 내가 입력을 받을 때 좌표값이 0이라면 zeroCnt++를 해주어서 수를 적어줘야 할 개수를 담아주었었다.

 

❓[2번째 포인트]

그리고 여기서 배울 점은 exit(0);

기존에 항상 백트래킹이나 DFS의 안타까운 점이 어떤 특정 조건을 만족시켜야 종료시킬 수 있는데 어떤 재귀에서 만족을 시켜도 다른 가지에서 종료가 되지 않기 때문에 무한 루프 사고를 많이 일으켰었다.

그래서 return은 함수를 종료시키지만 exit(0)을 통해 프로그램 자체를 종료시킬 수 있는 포인트를 배울 수 있었다.

 

이건 왜 시간 초과가 나오냐면 이중 for문을 통해 0이 있는 좌표 값을 (1, 1)부터 탐색한다.

그리고 나면 또다시 (1, 1)부터 0이 있는 좌표값을 탐색한다.

이 부분이 굉장히 시간이 낭비되는 포인트다.

void dfs(int cnt, int zeroCnt) {
	if (cnt == zeroCnt) {
		for (int i = 1; i <= 9; i++) {
			for (int j = 1; j <= 9; j++) {
				cout << map[i][j] << ' ';
			}
			cout << '\n';
		}
		exit(0);
	}

	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			if (map[i][j] == 0) {
				for (int k = 1; k <= 9; k++) {
					if (!row[i][k] && !col[j][k] && !block[checkBlock(i, j)][k]) {
						map[i][j] = k;
						col[j][k] = 1;
						row[i][k] = 1;
						block[checkBlock(i, j)][k] = 1;
						//cout << '-' << '\n';
						dfs(cnt + 1, zeroCnt);
						//cout << '+' << '\n';
						map[i][j] = 0;
						col[j][k] = 0;
						row[i][k] = 0;
						block[checkBlock(i, j)][k] = 0;
					}
				}
			}
		}
	}
}

 

❓[3번째 포인트]

그래서 (1, 1)부터 하되 다음 재귀 DFS에서는 (1, 2)로 시작을 하게끔 이중 for문을 버려준다.

>> 그렇다면 다음 좌표값을 넘겨주는 방법은?

 

아예 인자 자체에 넘겨주는 방법도 있고,

(j가 10 이상이 되면 i에 1을 더하고 j를 1로 바꿔준다.)

void dfs(int cnt, int i, int j) {
	if (cnt == 81) {
		for (int i = 1; i <= 9; i++) {
			for (int j = 1; j <= 9; j++) {
				cout << map[i][j] << ' ';
			}
			cout << '\n';
		}
		exit(0);
	}

	if (j > 9) {
		j = 1;
		i += 1;
	}

	if (map[i][j] == 0) {
		for (int k = 1; k <= 9; k++) {
			if (!row[i][k] && !col[j][k] && !block[checkBlock(i, j)][k]) {
				map[i][j] = k;
				col[j][k] = 1;
				row[i][k] = 1;
				block[checkBlock(i, j)][k] = 1;
				//cout << '-' << '\n';
				dfs(cnt + 1, i, j + 1);
				//cout << '+' << '\n';
				map[i][j] = 0;
				col[j][k] = 0;
				row[i][k] = 0;
				block[checkBlock(i, j)][k] = 0;
			}
		}
	}
	else {
		dfs(cnt + 1, i, j + 1);
	}
}

cnt가 좌표 개수이기 때문에 이를 활용하여 좌표값을 넣어주는 방법이 있다.

void dfs(int cnt) {
	if (cnt == 81) {
		for (int i = 1; i <= 9; i++) {
			for (int j = 1; j <= 9; j++) {
				cout << map[i][j] << ' ';
			}
			cout << '\n';
		}
		exit(0);
	}

	int i = (cnt / 9) + 1;
	int j = (cnt % 9) + 1;
	if (map[i][j] == 0) {
		for (int k = 1; k <= 9; k++) {
			if (!row[i][k] && !col[j][k] && !block[checkBlock(i, j)][k]) {
				map[i][j] = k;
				col[j][k] = 1;
				row[i][k] = 1;
				block[checkBlock(i, j)][k] = 1;
				//cout << '-' << '\n';
				dfs(cnt + 1);
				//cout << '+' << '\n';
				map[i][j] = 0;
				col[j][k] = 0;
				row[i][k] = 0;
				block[checkBlock(i, j)][k] = 0;
			}
		}
	}
	else {
		dfs(cnt + 1);
	}
}

---

[AC 코드]

#include <iostream>
using namespace std;

int map[10][10];
bool col[10][10]; // [~행][~숫자가 있는가]
bool row[10][10];
bool block[10][10];

int checkBlock(int r, int c) {
	int y = ((r - 1) / 3);
	int x = ((c - 1) / 3) + 1;

	return y * 3 + x;
}

void dfs(int cnt) {
	if (cnt == 81) {
		for (int i = 1; i <= 9; i++) {
			for (int j = 1; j <= 9; j++) {
				cout << map[i][j] << ' ';
			}
			cout << '\n';
		}
		exit(0);
	}

	int i = (cnt / 9) + 1;
	int j = (cnt % 9) + 1;
	if (map[i][j] == 0) {
		for (int k = 1; k <= 9; k++) {
			if (!row[i][k] && !col[j][k] && !block[checkBlock(i, j)][k]) {
				map[i][j] = k;
				col[j][k] = 1;
				row[i][k] = 1;
				block[checkBlock(i, j)][k] = 1;
				//cout << '-' << '\n';
				dfs(cnt + 1);
				//cout << '+' << '\n';
				map[i][j] = 0;
				col[j][k] = 0;
				row[i][k] = 0;
				block[checkBlock(i, j)][k] = 0;
			}
		}
	}
	else {
		dfs(cnt + 1);
	}
}

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

	int zeroCnt = 0;
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0) {
				zeroCnt++;
			}
			else {
				row[i][map[i][j]] = true;
				col[j][map[i][j]] = true;
				block[checkBlock(i, j)][map[i][j]] = true;
			}
		}
	}

	dfs(0);
	return 0;
}

---

느낀 점

오래간만에 백트래킹이라 그런지 백트래킹에 도입된 테크닉 마저 한 번에 처리하려니 좀 힘들었다.

그래도 exit(0);이라는 함수를 알게 되고, 백트래킹의 아쉬운 점을 보완할 수 있게 되었다.