[백준 알고리즘][백트래킹] 2580번 스도쿠

문제 정의

평소에 일반적으로 푸는 스도쿠와 같은 문제이다. 채워지지 않은 칸은 0으로 주어지면 모든 빈 칸이 채워진 스도쿠의 최종 모습을 출력하는 문제이다. 스도쿠에서 각각 세로와 가로 한줄씩은 1~9의 숫자가 하나씩 들어가야하고, 3*3의 칸으로 나눈 총 9개의 3*3 정사각형 안에서도 1~9의 숫자는 하나씩 존재해야한다.

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/2580)

문제 풀이

빈칸이 발견될 때마다 백트래킹 함수를 호출해서 빈칸에 알맞는 숫자를 찾아야 한다. 만족해야하는 조건은 3가지이므로 차례대로 체크를 하고 만약 조건에 만족하지 못할경우 다시 돌아가서 새로운 수를 채워넣고 다시 조건을 검사한다. 즉, 채우는 수는 1~9 로 차례대로 시도하고 가로, 세로, 3*3 정사각형 안에서 중복되는 숫자가 발견되는 경우 바로 다시 돌아가면 된다. 첫번째로 가로줄을 먼저 검사하고 두번째는 세로줄을 검사한다. 세번째는 해당 자리가 3*3 사각형의 몇번째에 속하는지 보고 범위안에서 검사를 한다. 시도한 숫자가 중복해서 발견되면 다시 돌아가는 것 자체가 너무 백트래킹 개념이랑 잘 맞는 것 같아서 이해가 잘 된다. 사실 머릿속으로 명확하게 정의되지 않는 부분은 3*3 어떤 사각형 안에 있는지를 판단해야하는지이다. 1~3, 4~6, 7~9로 나눠서 케이스문을 써도 될 것 같은데 약간 비효율적이게 복잡한 것 같다. 일단 저 방법을 생각해두고 앞의 조건을 처리하면서 좋은 방법이 있는지 생각해봐야겠다.

케이스문으로 코드는 완성했는데 만약 두번째 자리를 채울 때 첫번째 자리를 잘못 채워버리면 두번째자리를 채우지 못하고 끝나게 되므로 다시 돌아가야한다. 그 부분을 추가해서 다시 고쳐야겠다.

*스도쿠 문제가 정말 백트래킹의 기본이 되는 문제라고 한다. 맞는 것 같다. 다른 백트래킹 문제를 풀다가 개념적으로 부족한 것 같아서 쉬운 문제이자 기본인 이 문제를 풀어봐야겠다고 생각했다.

+추가 2018.11.09

이걸 처음 풀 때는 왜 어렵다고 생각이 들었지? 지난번에 짠 코드를 열어봤는데 너무나 엉망진창임을 느꼈다! 모든 조건들을 너무 보기 어렵게 짜져있었다. 그래서 왜 틀렸는지 찾아낼 힘이 없어졌다. 무튼 이번에 풀 때는 당연히 백트래킹써서 풀면 되겠다! 하는 생각으로 바로 구현을 해봤다. 그런데 틀렸습니다를 폭탄으로 맞았다. 예시 케이스가 하나뿐이라서 다른 입력값을 넣어보면서 해봐야겠다는 생각이 들었는데 예시 코드도 제대로 돌아가지 않는 거였다! 조건을 체크해주는 if문이 반대로 되어있었고 백트래킹 즉 한번 거꾸로 돌아갔는데도 안되는 경우 다시 또 돌아가주는 부분에서 조건문이 ==을 써야하는데 != 가 써있는 아주 바보같은 실수가 있었다. 잘못되었다고 의심이 되는 부분을 보면서 한번씩 컴파일 할 때마다 계속 고려해줘야 되는 부분들이 생각나서 고치니 해결! 한시간 걸렸으니 나쁘지 않은 발전이라 생각한다. 사실 근데 백트래킹으로 푼다 해놓고 돌아갈 때 값 바꿔주는 걸 안해놓고 제출도 했었다. 꼼꼼하게 생각하며 풀어야 겠다! 아 그리고 스도쿠에서 정사각형을 체크해주는 부분에서 틀렸다고 할 순 없지만 나는 또 방법을 떠올리지 못해서 case 9가지로 나눠서 for문을 만들고 check를 해줬는데 자기가 속해있는 정사각형만 안다면 상당히 짧게 코드를 짤 수 있는 것 같다. x < 3일 때는 for문에서 x의 조건이 0에서 시작하고 x >= 3 && x < 6 일 때는 x가 3부터 시작해야한다. (x/3)*3 (y/3)*3 로 이중 for문을 구현해주면 for문 하나만 코드에 있어도 가능하다! 

코드

#include<iostream>

#include<vector>

#include<cstdio>

using namespace std;

int board[10][10];

int check[10]; //1~9체크하려고

vector<pair<int, int>> tmp; //비어있는 좌표

vector<pair<int, int>> stack; //first는 몇번째 tmp인지 second는 몇번까지 넣어봤는지

bool check_square(int x, int y);

bool check_range(int x, int y);

void back(){

int i, j;

pair<int, int> curr;

for(i=0; i<tmp.size(); i++){ //한 좌표씩 값을 넣어보자!

curr = tmp[i];

for(j=1; j<10; j++){

board[curr.first][curr.second] = j;

if(check_range(curr.first, curr.second) == true && check_square(curr.first, curr.second) == true){

stack.push_back(make_pair(i, j)); //i번째 tmp에 j를 넣어서 성공한거

break;

}

if(j == 9){ //돌아가야함

while( j == 9 ){

board[curr.first][curr.second] = 0;

i = stack.back().first;

curr = tmp[stack.back().first];

j= stack.back().second;

stack.pop_back();

}

}

}

}

}

bool check_square(int x, int y){

int i, j;

for(i=1; i<10; i++)

check[i] = 0;

x = (x/3)*3;

y = (y/3)*3;

for(i=x; i<x+3; i++){

for(j=y; j<y+3; j++){

check[board[i][j]]++;

}

}

for(i=1; i<10; i++)

if(check[i] >= 2)

return false;

return true;

}

bool check_range(int x, int y){

int i, j;

for(i=0; i<10; i++)

check[i] = 0;

for(i=0; i<9; i++){

check[board[x][i]]++;

}

for(i=1; i<10; i++){

if(check[i] >= 2)

return false;

}

for(i=0; i<10; i++)

check[i] = 0;

for(i=0; i<9; i++){

check[board[i][y]]++;

}

for(i=1; i<10; i++){

if(check[i] >= 2)

return false;

}

return true;

}

int main(){

for(int i=0; i<9; i++){

for(int j=0; j<9; j++){

scanf("%1d", &board[i][j]);

if(board[i][j] == 0){

tmp.push_back(make_pair(i, j));

}

}

}

back();

for(int i=0; i<9; i++)

{

for(int j=0; j<9; j++)

cout<<board[i][j]<<' ';

cout<<endl;

}

return 0; 

}