[백준] 2239번: 스도쿠 (c++)

 

문제

---

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

 

2239번: 스도쿠

 

문제조건

---

답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다.

 

풀이

---

스도쿠를 풀면 되는 문제이다. 가로, 세로, 정사각형을 확인하며 가능한 숫자를 넣어본다. 단, 그때그때 각 조건을 확인하다보면 시간 초과가 일어남으로 이미 사용하고 있는 숫자들을 체크해 놓는 방식으로 진행해야 한다.

브르트포스 방식으로 풀어주었다. 0번째 row부터 돌며 비어있는(값이 '0'인) 곳을 만나면 1부터 9까지의 숫자를 넣으며 값을 확인해본다. 그 숫자가 가능하다면 값을 넣고, 다음 col의 값을 확인해본다. col은 8까지만 가능함으로 값이 8이라면 다음 row를 확인한다.

사실 답이 여러 개 있다면 사전식으로 앞서는 것을 출력한다는 조건을 읽지 않고 풀었는데 맞았다. 아마 1부터 돌며 그 숫자가 가능한지 확인했기 때문에 사전식으로 가장 앞서는 것을 출력하는 것 같다. 입력이 당연히 띄어쓰기가 있을 줄 알고 int형으로 풀었는데 알고보니 한 줄로 쭉 입력되는 거라 char형으로 받아서 int형으로 바꿔 주었다. 출력할 때 exit쓰는게 뭔가 맘에 안들지만 다른 방법이 생각이 안난다...

 

코드

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

char board[9][9];
bool check_row[9][10];
bool check_col[9][10];
bool check_square[9][10];

void sudoku(int r, int c) {
	if (r == 9) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				cout << board[i][j];
			}cout << "\n";
		}
		exit(0);
	}

	if (board[r][c] != '0') c == 8 ? sudoku(r + 1, 0) : sudoku(r, c + 1);

	if (board[r][c] == '0') {
		for (int i = 1; i <= 9; i++) {
			if (!check_row[r][i] && !check_col[c][i] && !check_square[(r / 3) * 3 + c / 3][i]) {
				check_row[r][i] = true;
				check_col[c][i] = true;
				check_square[(r / 3) * 3 + c / 3][i] = true;
				board[r][c] = i + '0';
				c == 8 ? sudoku(r+1, 0) : sudoku(r, c + 1);
				board[r][c] = '0';
				check_row[r][i] = false;
				check_col[c][i] = false;
				check_square[(r / 3) * 3 + c / 3][i] = false;
			}
		}
	}

}

int main() {
	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			char n; cin >> n;
			board[i][j] = n;
			if (n != '0') { 
				check_row[i][n - '0'] = true; //i번째 row에 숫자 n이 있음
				check_col[j][n - '0'] = true; //j번째 col에 숫자 n이 있음
				check_square[(i / 3)*3 + j / 3][n - '0'] = true; // (i / 3)*3 + j / 3  번째 사각형에 n이 있음
			}
		}
	}

	sudoku(0, 0);
}