[백준 2580번 C++] 스도쿠

1. 문제 링크

www.acmicpc.net/problem/2580

2580번: 스도쿠

 

 

 

2. 문제 설명

빈칸이 0으로 표시된 스도쿠판을 입력받은 후, 모든 빈칸이 채워진 스도쿠 판의 최종 모습을 출력하는 문제입니다.

스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않고, 스도쿠 판을 채우는 방법이 여럿인 경우에는 그중 하나만 출력하면 됩니다.

 

스도쿠판을 채우려면 다음 세 가지 조건을 모두 만족해야 합니다.

1. 한 행(row)에는 1부터 9까지 숫자가 한 번씩만 사용되어야 한다.

2. 한 열(col)에는 1부터 9까지 숫자가 한 번씩만 사용되어야 한다.

3. 3 * 3으로 나눈 정사각형 안에는 1부터 9까지 숫자가 한 번씩만 사용되어야 한다.

 

(0, 0) 0	(0, 1) 0	(0, 2) 0	(0, 3) 1	(0, 4) 1	(0, 5) 1	(0, 6) 2	(0, 7) 2	(0, 8) 2
(1, 0) 0	(1, 1) 0	(1, 2) 0	(1, 3) 1	(1, 4) 1	(1, 5) 1	(1, 6) 2	(1, 7) 2	(1, 8) 2
(2, 0) 0	(2, 1) 0	(2, 2) 0	(2, 3) 1	(2, 4) 1	(2, 5) 1	(2, 6) 2	(2, 7) 2	(2, 8) 2
(3, 0) 3	(3, 1) 3	(3, 2) 3	(3, 3) 4	(3, 4) 4	(3, 5) 4	(3, 6) 5	(3, 7) 5	(3, 8) 5
(4, 0) 3	(4, 1) 3	(4, 2) 3	(4, 3) 4	(4, 4) 4	(4, 5) 4	(4, 6) 5	(4, 7) 5	(4, 8) 5
(5, 0) 3	(5, 1) 3	(5, 2) 3	(5, 3) 4	(5, 4) 4	(5, 5) 4	(5, 6) 5	(5, 7) 5	(5, 8) 5
(6, 0) 6	(6, 1) 6	(6, 2) 6	(6, 3) 7	(6, 4) 7	(6, 5) 7	(6, 6) 8	(6, 7) 8	(6, 8) 8
(7, 0) 6	(7, 1) 6	(7, 2) 6	(7, 3) 7	(7, 4) 7	(7, 5) 7	(7, 6) 8	(7, 7) 8	(7, 8) 8
(8, 0) 6	(8, 1) 6	(8, 2) 6	(8, 3) 7	(8, 4) 7	(8, 5) 7	(8, 6) 8	(8, 7) 8	(8, 8) 8

스도쿠판을 2차원 배열로 표현한 표 입니다.

괄호 안의 숫자는 행과 열을 나타내고, 괄호 옆의 숫자는 몇 번째 3 * 3으로 나눈 정사각형인지 표시했습니다.

 

1번 조건을 확인하기 위해 bool check_row[9][10]배열을 만들어서 각각의 row에 1부터 9까지 숫자가 쓰였으면,

check_row[row][num]을 true로, 안 쓰였으면 false로 표시합니다.

넣을 수 있는 숫자가 1 ~ 9이므로 이 숫자를 그대로 index로 사용하기 위해 10칸으로 선언해줍니다. 

예를 들어 스도쿠의 0번째 행이 문제에서 제공하는 예제처럼 0, 3, 5, 4, 6, 9, 2, 7, 8인 경우

check_row[0] = [false, false, true, true, true, true, true, true, true, true] 입니다.

check_row[0][0]은 사용하지 않는 칸이므로 처음 초기화 된 대로 false이고,

check_row[0][1]은 0번째 행에 숫자 1이 사용되지 않았으므로 false입니다.

check_row[0][2]는 0번째 행에 숫자 2가 사용됐으므로 true입니다.

2번 조건은 1번 조건과 같은 방법으로 bool check_col[9][10]배열을 만들어 사용합니다.

예를 들어 스도쿠의 0번째 열이 문제에서 제공하는 예제처럼 0, 7, 0, 3, 8, 5, 9, 6, 2인 경우

check_col[0] = [false, false, true, true, false, true, true, true, true, true] 입니다.

3번 조건은 check_square[9][10]배열을 만들어서 각각의 square에 1부터 9까지 숫자가 쓰였으면,

check_square[square][num]을 true로, 안 쓰였으면 false로 표시합니다.

이 때, square(몇 번째 3 * 3으로 나눈 정사각형인지)을 row, col을 이용해서 구해보면 ((row / 3) * 3) + (col / 3)임을 알 수 있습니다.

예를 들어 스도쿠의 0번째 3 * 3으로 나눈 정사각형이 문제에서 제공하는 예제처럼 0, 3, 5, 7, 8, 2, 0, 6, 0인 경우

check_square[0] = [false, false, true, true, false, true, true, true, true, false] 입니다.

 

 

 

3. 소스코드

BOJ 2580번 스도쿠 C++ 풀이입니다.

#include <iostream>
using namespace std;

int map[9][9];
bool check_row[9][10];
bool check_col[9][10];
bool check_square[9][10];

void sudoku(int row, int col)
{
	if (row == 9) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++)
				cout << map[i][j] << ' ';
			cout << '\n';
		}
		exit(0);
	}

	if (map[row][col] != 0)
		col == 8 ? sudoku(row + 1, 0) : sudoku(row, col + 1);
	else {
		for (int num = 1; num <= 9; num++) {
			if (check_row[row][num] || check_col[col][num] || check_square[((row / 3) * 3) + (col / 3)][num])
				continue;
			map[row][col] = num;
			check_row[row][num] = true;
			check_col[col][num] = true;
			check_square[((row / 3) * 3) + (col / 3)][num] = true;
			col == 8 ? sudoku(row + 1, 0) : sudoku(row, col + 1);
			map[row][col] = 0;
			check_row[row][num] = false;
			check_col[col][num] = false;
			check_square[((row / 3) * 3) + (col / 3)][num] = false;
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> map[i][j];
			if (map[i][j] != 0) {
				check_row[i][map[i][j]] = true;
				check_col[j][map[i][j]] = true;
				check_square[((i / 3) * 3) + (j / 3)][map[i][j]] = true;
			}
		}
	}

	sudoku(0, 0);

	return 0;
}

4번 라인 : 스도쿠판을 저장할 배열 map[9][9]를 선언합니다.

5번 라인 : 현재 행에 사용된 숫자를 확인하기 위해 bool check_row[9][10]을 선언합니다.

6번 라인 : 현재 열에 사용된 숫자를 확인하기 위해 bool check_col[9][10]을 선언합니다.

7번 라인 : 현재 3 * 3 으로 나눈 정사각형에 사용된 숫자를 확인하기 위해 bool check_square[9][10]을 선언합니다.

44, 45, 46번 라인 : 스도쿠를 입력받습니다.

47번 라인 : 입력받은 수(map[i][j])가 0이 아니면,

48번 라인 : 현재 행 i에 숫자 map[i][j]이 사용되었음을 표시하기 위해 check_row[i][map[i][j]]에 true를 대입합니다.

49번 라인 : 현재 열 j에 숫자 map[i][j]이 사용되었음을 표시하기 위해 check_col[j][map[i][j]]에 true를 대입합니다.

50번 라인 : 현재 3 * 3으로 나눈 정사각형 ((i / 3) * 3) + (j / 3)에 숫자 map[i][j]이 사용되었음을 표시하기 위해

check_square[((i / 3) * 3) + (j / 3)][map[i][j]]에 true를 대입합니다.

55번 라인 : (0, 0)부터 스도쿠를 풀기 위해 sudoku(0, 0)을 호출합니다.

11번 라인 : 스도쿠는 9행이므로 row는 0 ~ 8인데 9가 되었으면 모든 행에 숫자를 넣어본 것이기 때문에

12 ~ 16번 라인 : 스도쿠를 출력하고,

17번 라인 : 스도쿠 판을 채우는 방법이 여럿인 경우에는 그중 하나만 출력해야 하기 때문에 프로그램을 종료합니다.

20번 라인 : map[row][col]이 0이 아닌 경우는 이미 숫자가 채워져 있기 때문에

21번 라인 : 다음칸(한 칸 오른쪽)을 확인하기 위해 sudoku(row, col + 1)을 호출합니다. 이때 col이 8인 경우 다음칸이 다음 열의 0번째 칸이기 때문에 sudoku(row + 1, 0)을 호출합니다.

22번 라인 : map[row][col]이 0인 경우 숫자를 채워봐야 하기 때문에

23번 라인 : 1부터 9까지 순서대로 for문을 돌립니다.

24, 25번 라인 : 같은 행에 이미 num을 사용했거나(check_row[row][num] == true), 같은 열에 이미 num을 사용했거나(check_col[col][num] == true), 같은 3 * 3으로 나눈 정사각형에 이미 num을 사용했으면(check_square[((row / 3) * 3) + (col / 3)][num] == true) 현재 칸(map[row][col])을 num으로 채울 수 없기 때문에 다음 숫자로 채워보기 위해 continue합니다.

26번 라인 : 24번 라인 if 조건의 값이 모두 false이면 현재 칸(map[row][col])을 num으로 채울 수 있으므로, map[row][col]에 num을 대입합니다.

27번 라인 : 현재 칸을 num으로 채웠으므로 현재 행에 num을 사용했다고 표시하기 위해 check_row[row][num]에 true를 대입합니다.

28번 라인 : 현재 칸을 num으로 채웠으므로 현재 열에 num을 사용했다고 표시하기 위해 check_col[col][num]에 true를 대입합니다.

29번 라인 : 현재 칸을 num으로 채웠으므로 현재 3 * 3으로 나눈 정사각형에 num을 사용했다고 표시하기 위해 check_square[((row / 3) * 3) + (col / 3)][num]에 true를 대입합니다.

30번 라인 :  현재 칸을 num으로 채웠으므로 다음 칸(한 칸 오른쪽)을 확인하기 위해 sudoku(row, col + 1)을 호출합니다. 이때 col이 8인 경우 다음칸이 다음 열의 0번째 칸이기 때문에 sudoku(row + 1, 0)을 호출합니다.

31번 라인 : 31번 라인이 실행될 때는 현재 칸을 num으로 채웠을 때의 경우의 수를 모두 실행해본 후 돌아온 것이기 때문에, 현재 칸을 num보다 큰 다른 숫자로 채웠을 경우의 수를 확인해보기 위해서 map[row][col]에 0을 대입하여 num을 지웁니다.

32, 33, 34번 라인 : map[row][col]에 num을 사용하지 않으므로, check_row[row][num], check_col[col][num], check_square[((row / 3) * 3) + (col / 3)][num]에 false를 대입해서 num을 사용하지 않았다는 표시를 해줍니다.