https://www.acmicpc.net/problem/2580
2580번: 스도쿠
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루
www.acmicpc.net
문제
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.
- 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
- 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
입력
아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
출력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
접근방법
backtracking으로 구현하였다.
1. 먼저 스도쿠 판에 비어있는 칸 개수를 센다. -> n
2. backtracking 진행
2-1. 가로 세로 3X3 조건에 부합하는 k 가 발견되면 탐색을 진행한다.
2-2. backtracking 진행시 depth가 n+1이 되면 모든 빈칸을 채운 후 정답을 도출함을 의미함으로 이를 result 배열에 담는다.
3. 하나의 정답을 도출한 후 fin변수를 통해 아직 다른 정답을 찾는 중인 함수 콜스택들을 종료시켜 준다.
4. 정답 출력
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n=0;
int b[10][10]={0};
int result[10][10];
int fin=0;
void bt(int depth, int b[][10]){
if(depth==n+1){
fin=1;
for(int i=1; i<=9; i++){
for(int j=1; j<=9; j++){
result[i][j] = b[i][j];
}
}
return ;
}
for(int i=1; i<=9; i++){
for(int j=1; j<=9; j++){
if(b[i][j]==0){
for(int k=1; k<=9; k++){
if(fin) return ;
b[i][j]=0;
//k가 적합하면 k 넣고 back tracking
bool pass = true;
for(int x=1; x<=9; x++){
if(b[x][j]==k || b[i][x]==k){
pass = false;
}
}
for(int x=((i-1)/3)*3+1; x<=((i-1)/3)*3+3; x++){
for(int y=((j-1)/3)*3+1; y<=((j-1)/3)*3+3; y++){
if(b[x][y]==k){
pass = false;
}
}
}
b[i][j]=k;
if(pass) bt(depth+1, b);
b[i][j]=0;
}
return ;
}
}
}
return ;
}
int main()
{
for(int i=1; i<=9; i++){
for(int j=1; j<=9; j++){
scanf("%d", &b[i][j]);
if(b[i][j]==0) n++;
}
}
bt(1, b);
for(int i=1; i<=9; i++){
for(int j=1; j<=9; j++){
printf("%d ", result[i][j]);
}
printf("\n");
}
}
느낀점
3X3 조건을 만족하는지를 확인할때 꼼꼼이 따지지 않고 범위를 정했다가 1~3범위를 0~2범위로 착각하여 디버깅 시간이 오래 걸렸다. 더 꼼꼼하게 생각하고 코딩해야 겠다.
'알고리즘 문제풀이' 카테고리의 다른 글
[백준] 9663번 N-Queen C++ (0) | 2021.08.01 |
---|---|
[백준] 14889번 스타트와 링크 c++ (0) | 2021.08.01 |
[백준] 11404번 플로이드 c++ (0) | 2021.07.25 |
[백준] 11657번 타임머신 c++ (0) | 2021.07.21 |
[백준] 9370번 미확인 도착지 c++ (0) | 2021.07.20 |