2580번 스도쿠
문제
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.
나머지 빈 칸을 채우는 방식은 다음과 같다.
- 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
- 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.
또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.
이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.
게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
입력
아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
출력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
예제 입력
0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0
예제 출력
1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1
해결방법
⭐️ 1차 시도 ⭐️
틀렸습니다
먼저 시간초과를 막기 위해 모든 노드를 탐색하지 않고 값이 0 인 노드만 따로 벡터로 관리한다
for(int i=0; i<9; i++){
for(int j=0; j<9; j++){
cin >> map[i][j];
if(map[i][j] == 0) blank.push_back(node(i,j));
}
}
이제 값이 0 인 노드를 채워야한다
1~9 까지의 숫자에서 가로, 세로, 박스를 확인하여 들어갈 수 있는 수를 확인한다
// 가로 체크
bool chk_col(int x,int y,int num){
for(int i=0; i<9; i++){
if(map[x][i] == num) return false;
}
return true;
}
// 세로 체크
bool chk_row(int x,int y,int num){
for(int i=0; i<9; i++){
if(map[i][y] == num) return false;
}
return true;
}
// 네모 체크
bool chk_box(int x,int y,int num){
int row = x - (x%3);
int col = y - (y%3);
for(int i=row; i<row+3; i++){
for(int j=col; j<col+3; j++){
if(map[i][j] == num) return false;
}
}
return true;
}
만약 세 조건 모두를 만족한다면 빈칸에 해당 숫자를 넣고 다음 빈칸으로 이동한다
// 수가 들어가도 되는지 체크하는 함수
bool is_possible(int x,int y,int num){
if(chk_col(x,y,num) && chk_row(x,y,num) && chk_box(x,y,num)){
return true;
}else{
return false;
}
}
하지만 DFS 에서 오류가 있었는지 결과가 나오지 않았다.... ㅠㅡㅠ
⭐️ 2차 시도 ⭐️
시간 초과
원래 문제에 접근하는대로 아래의 두가지 파트로 나눠 구현했다
- 정답을 찾은 경우
- 재귀를 통한 DFS 탐색
void dfs(int ind,int cnt){
if(cnt == blank.size()){
print_sdoku();
exit(0);
}
for(int i=ind; i<blank.size(); i++){
int x = blank[i].first;
int y = blank[i].second;
for(int k=1; k<=9; k++){
if(is_possible(x,y,k)){
map[x][y] = k;
dfs(i,cnt+1);
map[x][y] = 0;
}
}
}
}
하지만 이 경우는 시간 초과가 발생했다
⭐️ 3차 시도 ⭐️
맞았습니다!
2차 시도했던 코드에서 vector를 돌며 DFS 탐색을 하는 부분을 삭제했다
결과는 맞았습니다! 가 나왔다
void dfs(int ind,int cnt){
int i = blank[ind].first;
int j = blank[ind].second;
// 스도쿠의 모든 빈 칸을 채웠다면
if(cnt == blank.size()){
printSdoku();
exit(0);
}
// 빈 칸에 1~9 까지의 경우를 넣음
// 스도쿠는 빈 칸이 존재할 수 없기 때문에, vector 를 반복문으로 넣지 않음
for(int num=1; num<=9; num++){
// i 가 빈 칸에 들어갈 수 있는지 확인
if(is_possible(i,j,num)){
map[i][j] = num;
dfs(ind+1,cnt+1);
map[i][j] = 0;
}
}
}
2차 시도를 위해 작성했던 코드는 결국 빈칸을 전부 채우지 않아도 되는 부분 순열의 문제의 코드였다
다시 말해서, 스도쿠 문제는 전체 빈칸을 채우는 경우만 유효하다
하지만 매 DFS 함수마다 blank 벡터를 돈다는 것은 빈칸의 모든 부분 순열을 체크한다는 얘기이다
따라서 vector를 돌지 않고, 1~9 까지만 반복문을 돌린다면 모든 칸을 채우는 경우만 체크하게된다
(꼭 다시 풀어보자!!! → 다시 풀어봄!!)
⏰ 시간 복잡도 ⏰
문제를 접하고 시간 복잡도에 대해 고민을 하다 질문을 올렷는데 이러한 답변이 왔다
이런 코드는 상한선을 적당히 계산할 수는 있겠지만 보드의 상태에 따라 너무나 많은 커팅이 일어나기 때문에 실제로 도는 속도와는 비교가 불가능할 것 같습니다. 커팅이 없다고 가정했을 때 각 줄에서 선택할 수 있는 수가 9가지씩이라고 가정하면 9^81이지만 실제로는 같은 행, 열, 3x3 사각형 내에 같은 수가 없는지를 체크하고 잘라내는 일들이 너무나 예측할 수 없게 발생하기 때문에 이 상한선은 크게 의미가 없습니다.
https://en.wikipedia.org/wiki/... 에서도 백트래킹 기법에 대해 설명하고 있지만 시간복잡도에 대한 이야기는 하지 않습니다.
소스코드
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 9
#define INF 987654321
using namespace std;
typedef pair<int,int> node;
int map[MAX][MAX];
vector<node> blank;
bool chk_row(int r,int c,int num){
for(int i=0; i<9; i++){
if(map[i][c] == num) return false;
}
return true;
}
bool chk_col(int r,int c,int num){
for(int i=0; i<9; i++){
if(map[r][i] == num) return false;
}
return true;
}
bool chk_box(int r,int c,int num){
int row = r - (r % 3);
int col = c - (c % 3);
for(int i=row; i<row+3; i++){
for(int j=col; j<col+3; j++){
if(map[i][j] == num) return false;
}
}
return true;
}
bool is_possible(int r,int c,int num){
// 만약 행,열,박스 모두 해당 숫자가 없다면 해당 빈칸에 숫자 넣을 수 있음
if(chk_row(r,c,num) && chk_col(r,c,num) && chk_box(r,c,num)){
return true;
}
return false;
}
void printSdoku(){
// 스도쿠 출력
for(int i=0; i<9; i++){
for(int j=0; j<9; j++){
cout << map[i][j] << " ";
}
cout << "\n";
}
}
void dfs(int ind,int cnt){
int i = blank[ind].first;
int j = blank[ind].second;
// 스도쿠의 모든 빈 칸을 채웠다면
if(cnt == blank.size()){
printSdoku();
exit(0);
}
// 빈 칸에 1~9 까지의 경우를 넣음
// 스도쿠는 빈 칸이 존재할 수 없기 때문에, vector 를 반복문으로 넣지 않음
for(int num=1; num<=9; num++){
// i 가 빈 칸에 들어갈 수 있는지 확인
if(is_possible(i,j,num)){
map[i][j] = num;
dfs(ind+1,cnt+1);
map[i][j] = 0;
}
}
}
int main(int argc, const char * argv[]) {
// cin,cout 속도향상
ios_base::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 >> map[i][j];
// 빈 칸이라면 black 벡터에 push
if(map[i][j]==0) blank.push_back(node(i,j));
}
}
dfs(0,0);
}
'Algorithm > BOJ 문제풀이' 카테고리의 다른 글
| [DFS] 10451번 순열 사이클 (0) | 2018.12.16 |
|---|---|
| [DFS] 1799번 비숍 (0) | 2018.12.16 |
| [DFS] 1743번 음식물 피하기 (0) | 2018.12.16 |
| [BFS] 2146번 다리 만들기 (0) | 2018.12.16 |
| [BFS] 3055번 탈출 (0) | 2018.12.14 |
