스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.
나머지 빈 칸을 채우는 방식은 다음과 같다.
각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.
또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.
이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.
게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
입력
아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
출력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
제한
baekjoon의 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 다음은 그 알고리즘의 수행 시간이다.
C++14: 80ms
Java: 292ms
PyPy3: 1172ms
진짜 어렵다.. 2차원 배열 행 열 처리가 헷갈린달 말이지...
그래도 n - queen 문제를 풀고 푸니까 어느정도 접근방법은 쉽게 생각할 수 있었다.
2차원 배열을 받음과 동시에, 0의 자리 숫자의 자리를 저장하고, 각 행당 들어갈 수 있는 숫자를 저장해서 풀려고 했었다.
풀다보니 인덱스 처리가 너무 복잡해지고 생각할게 많아 그냥 저장해둔 0의 자리에 1~9까지 넣어주고, 행, 열, 사분면? 중복 체크를 해 주었다.
그 후 내가 넣어준 숫자를 다시 0처리를 해줘야 정답 처리가 되었다.
package BackTracking;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
public class boj2580_스도쿠 {
static int map[][] = new int[9][9];
static ArrayList[] visit = new ArrayList[9]; //positive number 방문
static ArrayList[] Positive_Number = new ArrayList[9]; //행 들어갈 수 있는 수
static ArrayList[] Zero_Position = new ArrayList[9]; //행마다 0인 위치
static boolean flag = false;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
for(int i=0;i<9;i++) {
Positive_Number[i] = new ArrayList<Integer>();
Zero_Position[i] = new ArrayList<Integer>();
visit[i] = new ArrayList<Integer>();
for(int j=1;j<=9;j++)
Positive_Number[i].add(j);
}
String temp[];
for(int i=0;i<9;i++) {
temp = br.readLine().split(" ");
//j:행
for(int j=0;j<9;j++) {
int number = Integer.parseInt(temp[j]);
map[i][j] = number;
//zero_position[행] = {행마다 들어 갈 수 있는 수}
if(number != 0) {
int index = Positive_Number[j].indexOf(number);
Positive_Number[j].remove(index);
}
else
Zero_Position[j].add(i); //0인 위치 (j,i)
}
}
for(int i=0;i<9;i++) {
for(int j=0;j<Positive_Number[i].size();j++)
visit[i].add(Positive_Number[i].get(j));
}
/*-------------------input Success -----------------------*/
//숫자 채우기
//type ( 행, zero 위치)
dfs(0,0);
}
//idx : 행
public static void dfs (int idx, int x_index) {
//마지막까지 도달 했거나, 그런 경우가 있을 때
if( idx==9) {
for(int i=0;i<9;i++) {
for(int j=0;j<8;j++)
System.out.print(map[i][j]+" ");
System.out.println(map[i][8]);
}
System.exit(0);//강제 종료
}
if(Zero_Position[idx].size()==0)
dfs(idx+1,0);
//idx 행
//0인 위치 ( , idx)
//각 행 당 빈자리
int x = (int) Zero_Position[idx].get(x_index);
for(int i=1;i<10;i++) {
map[x][idx] = i;
if(check(x, idx)) {
if(x_index == Zero_Position[idx].size()-1)
dfs(idx+1,0);
else
dfs(idx,x_index+1);
}
map[x][idx] = 0;
}
}
//열 중복, 3*3 중복 확인
public static boolean check(int x, int y) {
//열 중복 체크
for(int i=0;i<9;i++) {
if(y==i)
continue;
int a = map[x][y];
int b = map[x][i];
if(a==b)
return false;
}
//행 중복 체크
for(int i=0;i<9;i++) {
if(x==i)
continue;
int a = map[x][y];
int b = map[i][y];
if(a==b)
return false;
}
int row = (x/3) *3;
int column = (y/3)*3;
//3*3 중복 확인
for(int i=row;i<row+3;i++) {
for(int j = column;j<column+3;j++) {
int a = map[x][y];
int b = map[i][j];
if(x==i && y==j)
continue;
else if(a ==b)
return false;
}
}
return true;
}
}
