[백준문제풀이] 2580 스도쿠

 

풀이일시 : 2020-12-15

​

문제 :

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

​

​

입력 :

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

​

​

출력 :

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

​

​

풀이 :

- 스도쿠를 완성하면된다.

( "스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다" -> 대각선 체크 X)

​

- map[][] 의 row 와 col 그리고 square에 있는 숫자들을 검사해야한다. row와 col 의 index는 1~9 까지 그대로 올라가면 될 것이고 square의 index는 squareindex함수에서 정의해 줄 것이다.

​

- sudoku (dfs함수) 함수를 만들고 index 0 으로 시작한다. index 0의 좌표는 0,0 이다. 이는 y=index/9; x=index%9 로 정의할 수 있을것이다.

​

- map[y][x] 가 0이 아니라면 다음칸에서(인덱스+1) sudoku를 다시 돌린다.

​

- map[y][x] 가 0이라면 조건에 맞추어 숫자를 채워준다.

map[y][x] = k;
col[x][k] = true;
row[y][k] = true;
square[squareindex(y, x)][k] = true;

 

그리고 인덱스+1 하여 sudoku 를 돌린다. 여기서 백트래킹을 사용해야한다.

​

​

=> 백트래킹의 동작에 대한 예시

​

입력을 다음과 같이 넣어준다.

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

 

index 0부터 계속 진행 하며 index가 14일때 멈춰보고 그때의 map 을 보자

1 2 3 4 5 6 7 8 9
4 5 6 1 2 3 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

이 후 진행해야 되는 15번째 인덱스의 값은 같은 row에 1~6이 있고 같은 square에 7~9가 있어서 어떤 숫자도 오지못할것이다. 따라서 그 이전값들을 바꿔줘야 할 것이다. sudoku(cnt+1) 을 빠져나오고

map[y][x] = 0;
col[x][k] = false;
row[y][k] = false;
square[squareindex(y, x)][k] = false;

로 다시 복귀시켜준다.

​

이와 같은 작업으로 백트래킹을 시켜주면 모든 경우에 대해서 알맞은 수를 찾아낼 수 있다.

​

#define MAX 9
#include <iostream>

using namespace std;
int map[MAX][MAX];
int row[MAX][10];
int col[MAX][10];
int square[MAX][10];
int squareindex(int y, int x) {
	return (y / 3) * 3 + x / 3;
}
void sudoku(int cnt) {
	//스도쿠 판을 채우는 방법이 여러개일 경우 하나만 출력하므로 81이 되면 그냥 출력해버리기
	if (cnt == 81) { //총 81칸이므로
		for (int i = 0; i < MAX; i++) {
			for (int j = 0; j < MAX; j++) {
				cout << map[i][j] << " ";
			}
			cout << endl;
		}
		exit(0);
	}
	int y = cnt / 9; //cnt에 대해 x,y 좌표를 지정해준다.
	int x = cnt % 9;
	if (map[y][x]) //0이 아니라면
		sudoku(cnt + 1); //다음칸에 대해 dfs 실행
	else {
		for (int k = 1; k <= MAX; k++) {
			if (!col[x][k] && !row[y][k] && !square[squareindex(y, x)][k]) { //다같이 한 숫자가 없다면
				map[y][x] = k;//map상의 0를 k로바꾼다.
				col[x][k] = true; //차례대로 col row square를 채운다.
				row[y][k] = true;
				square[squareindex(y, x)][k] = true;
				sudoku(cnt + 1);
				//하지만 위의 숫자 k가 정답이 아닐수도 있다. k++가 진행되면서 조건에 맞는 다른 숫자가 정답일 수 있다.
				//따라서 이것이 아닐경우 지워주는 작업도 진행해주어야한다.
				map[y][x] = 0;
				col[x][k] = false;
				row[y][k] = false;
				square[squareindex(y, x)][k] = false;
				
			}
		}
	}
}
int main() {
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			cin >> map[i][j];
			if (map[i][j]) { //0이 아닌 수가 입력되었다면
				col[j][map[i][j]] = true;
				row[i][map[i][j]] = true;
				square[squareindex(i, j)][map[i][j]] = true;
			}
		}
	}
	sudoku(0);
	return 0;
}

 

참고자료 : backtracking

dbstndi6316.tistory.com/37

[개념정리] Backtracking 백트래킹