궤도
[백준] 2580번 : 스도쿠 본문
문제
풀이
입력을 어떻게 처리하여 어떤 순서로 스도쿠의 빈공간을 채워나갈지 고민을 많이했다.
처음에는 1행->9행으로 값을 채우고 그 다음에 1열->9열로 값을 채우고 마지막으론 구역별로..?라고 생각하다가
너무 복잡해질 것 같다는 생각이 들었다. 그러다 내가 실제로 스도쿠를 볼 때 어떻게 푸는지 생각했다.
보통 사람들은 먼저 빈공간을 찾아가서 그 공간의 행, 열, 구역을 한번에 확인한 뒤 값을 채워나간다.
그럼 코드도 이런식으로 짜면되지 않을까? 싶었다. 입력을 받으면서 빈공간을 봐둔 다음에 각각의 빈공간마다 1~9를 넣어보면서 그 공간의 행, 열, 구역의 숫자와 비교하면 될 것 같았다. 이 아이디어를 떠올리니 나머지는 크게 어렵지 않았다.
소스코드
#include <iostream>
using namespace std;
int sudoku[9][9];
int hole_cnt = 0;
bool found = false;
struct hole {
int row, col;
};
hole* sudo_hole = new hole[81]; //빈공간 저장
bool promising(int hole_index, int candidate) {
int i, j;
for (i = 0; i < 9; i++) {
if (sudoku[sudo_hole[hole_index].row][i] == candidate) //같은 행에 있나?
return false;
if (sudoku[i][sudo_hole[hole_index].col] == candidate) //같은 열에 있나?
return false;
}
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
if ((sudo_hole[hole_index].row / 3) == (i / 3) && (sudo_hole[hole_index].col / 3) == (j / 3)) { //같은 구역에 있나?(이거 생각하느라 고생함)
if (sudoku[i][j] == candidate)
return false;
}
}
}
return true;
}
void fill_sudoku(int cnt) {
if (cnt == hole_cnt) { //다 찾으면 출력
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cout << sudoku[i][j] << ' ';
}
cout << '\n';
}
found = true; //첫 해 찾았으면 바로 나오기
}
else {
for (int i = 1; i <= 9; i++) {
if (promising(cnt, i)) {
sudoku[sudo_hole[cnt].row][sudo_hole[cnt].col] = i; //아래로 내려감
fill_sudoku(cnt + 1);
if (found)
return;
sudoku[sudo_hole[cnt].row][sudo_hole[cnt].col] = 0; //위로 다시 올라감(이거 빼먹어서 고생함. 돌아갈 길을 만들어 두자)
}
}
}
}
int main() {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cin >> sudoku[i][j];
if (sudoku[i][j] == 0) {
sudo_hole[hole_cnt].row = i;
sudo_hole[hole_cnt++].col = j;
}
}
}
fill_sudoku(0);
}전체 소스코드이다.
int sudoku[9][9];
int hole_cnt = 0;
bool found = false;
struct hole {
int row, col;
};
hole* sudo_hole = new hole[81]; //빈공간 저장입력을 받을 스도쿠판 하나를 준비하고 빈공간을 저장할 sudo_hole 구조체 배열을 준비한다. 이제보니 이건 pair로 해봐도 될 것 같다.
빈공간의 전체 갯수를 알아야 함수의 종료조건을 설정할 수 있으니 hole_cnt에 저장한다.
bool 변수인 found의 용도는 이따가 설명하도록 하겠다.
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cin >> sudoku[i][j];
if (sudoku[i][j] == 0) {
sudo_hole[hole_cnt].row = i;
sudo_hole[hole_cnt++].col = j;
}
}
}main에서 입력을 처리하는 부분이다. 빈공간 즉 0을 발견하면 해당 위치의 행과 열을 저장한다.
void fill_sudoku(int cnt) {
if (cnt == hole_cnt) { //다 찾으면 출력
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
cout << sudoku[i][j] << ' ';
}
cout << '\n';
}
found = true; //첫 해 찾았으면 바로 나오기
}
else {
for (int i = 1; i <= 9; i++) {
if (promising(cnt, i)) {
sudoku[sudo_hole[cnt].row][sudo_hole[cnt].col] = i; //아래로 내려감
fill_sudoku(cnt + 1);
if (found)
return;
sudoku[sudo_hole[cnt].row][sudo_hole[cnt].col] = 0; //위로 다시 올라감(이거 빼먹어서 고생함. 돌아갈 길을 만들어 두자)
}
}
}
}스도쿠판에 값을 채우는 fill_sudoku 함수이다. 기존 백트래킹 함수의 종료조건과 매우 유사하나 마지막에 found = true가 있는 것을 볼 수 있다. 해당 문제는 정답이 여러 개일 수 있고, 우리는 제일 먼저 찾은 최초의 답만 출력할 것이기 때문에 첫번째 답을 찾은 뒤 더이상 함수가 돌아가지 않도록 found를 true로 놓고 if(found)일 때 return하여 대기중이던 모든 함수를 종료해주는 것이다.
특정 빈 공간에 대해 1~9까지의 숫자들 중 어떤 숫자(i)를 넣을 수 있는지 promising 함수로 확인한다. 만약 넣을 수 있는 수를 발견한다면 숫자를 입력하고, fill_sudoku(cnt + 1)을 호출해 다음 빈 공간으로 넘어간다.
그리고 이 부분이 중요한데, 백트래킹 함수를 구현할 때 신경써야 하는 것은 상위노드로 되돌아갈 수 있는 길을 마련해 두는 것이다.
1~9의 숫자를 탐색하던 중 2가 조건을 충족하여 투입된 상황을 가정해보자. 근데 그 뒤에 빈 공간을 채우다 보니 해당 위치에 2를 채웠을 땐 스도쿠를 완성할 수 없다는 것을 알게된 것이다. 그럴 땐 해당 위치를 다시 0으로 초기화 하고 3부터 다시 탐색하며 투입될 수 있는 또다른 수가 없는지 확인해야 한다. 어찌보면 기본이나 마찬가지인데 이 부분을 잊어 잠시 고생했다.
bool promising(int hole_index, int candidate) {
int i, j;
for (i = 0; i < 9; i++) {
if (sudoku[sudo_hole[hole_index].row][i] == candidate) //같은 행에 있나?
return false;
if (sudoku[i][sudo_hole[hole_index].col] == candidate) //같은 열에 있나?
return false;
}
for (i = 0; i < 9; i++) {
for (j = 0; j < 9; j++) {
if ((sudo_hole[hole_index].row / 3) == (i / 3) && (sudo_hole[hole_index].col / 3) == (j / 3)) { //같은 구역에 있나?(이거 생각하느라 고생함)
if (sudoku[i][j] == candidate)
return false;
}
}
}
return true;
}마지막으로 특정 숫자가 이 공간에 들어갈 수 있는지 체크하는 promising 함수를 살펴보자.
이 공간에 들어올 가능성이 있는 숫자(candidate)에 대해 해당 위치에 열과 행을 살펴보며 이 숫자와 같은 수가 이미 입력되어 있는 것은 아닌지 확인한다.
그리고나서 3x3의 구역을 확인해야 하는데 이 부분을 어떻게 구현할지 고민하는데 시간이 걸렸다.
내가 사용한 방법은 간단히 말하자면 9x9의 판을 3x3으로 압축한 것이다.
귀찮아서 모든 좌표를 쓰진 않았지만 아무튼 이렇게 각 좌표를 3으로 나눠 몫을 취하면 구역별로 같은 좌표값을 갖게 된다.
이렇게 같은 구역에 대해 중복되는 수를 체크하는 것도 처리했다.
이 모든 조건을 통과했다면 true 반환
