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

문제

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

2580번: 스도쿠

---

문제 요약

빈 칸이 0으로 주어진 9 × 9 스도쿠를 모두 채워 출력한다.

 

규칙

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

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

---

코드

#include <iostream>

using namespace std;

int board[9][9]; // 스도쿠판

// 0 ~ 8번 가로, 세로, 사각형 존재한다고 가정

bool row[9][10]; // row[i][j]: i번째 가로줄에 j라는 숫자 존재
bool col[9][10]; // col[i][j]: i번째 세로줄에 j라는 숫자 존재
bool square[9][10]; // square[i][j]: i번째 사각형에 j라는 숫자 존재

// (x, y)에 해당하는 좌표는 (x / 3) * 3 + (y / 3)번째 사각형에 해당
// (사각형의 번호가 세로는 3씩 증가, 가로는 1씩 증가하므로)

// 스도쿠 판 출력
void printBoard() {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cout << board[i][j] << " ";
		}
		cout << "\n";
	}
}

void dfs(int cnt) { 
	// cnt는 지금까지 차례대로 스도쿠 판을 채운 수의 개수 (탐색 횟수 = 깊이)

	int x = cnt / 9; // 현재 채울 수의 x좌표
	int y = cnt % 9; // 현재 채울 수의 x좌표

	// 스도쿠 판이 모두 채워졌다면 출력
	if (cnt == 81) {
		printBoard();
		exit(0); // 종료
	}

	// 해당 칸이 비어있으면 
	if (board[x][y] == 0) {
		// 1부터 9까지 되는 숫자 탐색
		for (int i = 1; i <= 9; i++) {
			if (!row[x][i] && !col[y][i] && !square[(x / 3) * 3 + (y / 3)][i]) {
				// 해당 칸에 i가 들어갔을 경우 체크
				row[x][i] = true;
				col[y][i] = true;
				square[(x / 3) * 3 + (y / 3)][i] = true;
				board[x][y] = i;
				dfs(cnt + 1);

				// 결국 판을 다 채우지 못하고 재귀를 빠져나왔다면, 다시 복구
				row[x][i] = false;
				col[y][i] = false;
				square[(x / 3) * 3 + (y / 3)][i] = false;
				board[x][y] = 0;

			}
		}
	}
	// 해당 칸에 숫자가 이미 있다면
	else {
		dfs(cnt + 1); // 다음 숫자 채우기
	}

}

int main() {
	// cin, cout 시간 최적화
	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 >> board[i][j];

			// 이미 채워진 숫자 체크
			if (board[i][j] != 0) {
				row[i][board[i][j]] = true;
				col[j][board[i][j]] = true;
				square[(i / 3) * 3 + (j / 3)][board[i][j]] = true;
			}
		}
	}

	dfs(0);

	return 0;
}

---

코드 설명

재귀를 이용한 완전 탐색 (백트래킹)으로 문제를 해결한다.

 

먼저 가로줄, 세로줄, 사각형 영역에 숫자 해당 숫자가 존재하는지 여부를 체크하는 2차원 배열 3개로 관리한다.

+ 초기 값은 입력을 받으면서 체크한다.

 

dfs 함수는 현재까지 재귀로 호출된 횟수를 인자(cnt)로 받고,  이는 (0, 0)부터 몇 번째 수인지를 나타낸다.

 

cnt를 통해 현재 채워야 하는 스도쿠 판의 좌표를 알 수 있고, 이를 통해 그 좌표가 몇 번째 줄 인지, 몇 번째 사각형 영역에 속해 있는지를 찾을 수 있다.

 

cnt가 81, 즉 스도쿠의 (7, 7) 마지막 인덱스에 해당한다면 스도쿠 판이 모두 채워졌다는 의미이므로 스도쿠 판을 출력하고, 프로그램을 종료한다.(프로그램을 종료하지 않으면, 만족하는 모든 경우의 수를 출력하므로 주의해야한다.)

 

스도쿠 판 내 사각형 영역의 번호를 아래처럼 가정했을 때,

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

 

사각형 영역 번호가 세로는 3씩 증가, 가로는 1씩 증가하므로, (x, y)에 해당하는 좌표는 (x / 3) * 3 + (y / 3)번째 사각형에 해당한다.

 

dfs를 진행하면서, 해당 좌표에 0 ~ 9 중에 가능한 숫자를 모두 넣어보고, 아니라면 (프로그램이 종료되지 않았다면) 넣은 숫자가 틀렸다는 것이므로 다시 숫자를 지워야 한다.