![[백준,BOJ 2580] 스도쿠 (JAVA 구현,추가풀이)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fb3jlpX%2FbtqzZKIOZXL%2FKDo3kX8PLucFaW2k1KA1tK%2Fimg.png)
-내 생각
여태 푼 백 트래킹 알고리즘을 이용하는 문제들 중 N-QUEEN문제만큼 고민 한 문제이다. 그래도 N-Queen문제를 한 번 풀어봤던 탓인지, 어떻게 풀어야 할지 감을 잡는데 오랜 시간이 걸리지는 않았다. 이 문제까지 풀어보고 느낀 건 백 트래킹 알고리즘의 경우 별도의 체크 메서드가 반드시 필요하다는 점이다. 글에서만 봤지만 무슨 소리인지 몰랐던 '유망한 노드'를 식별하는데 필요하다고 생각한다. 즉, 조건에 해당하는 사항만 DFS로 재귀호출을 해주면 된다.
우선 스도쿠 문제의 경우 대다수의 사람들이 조건을 알 거라고 생각한다. 물론 문제에도 쓰여있다. 즉 가로, 세로, 3X3크기의 박스에 1부터 9까지의 숫자가 겹치지 않고 들어가야 한다. 여기까지만 읽으면 백 트래킹을 위한 조건을 어떻게 세워야 할지 감이 잡힐 것이다. 현재의 스도쿠판에 빈 자리에 1~9의 숫자를 넣어가며 가로에 겹치는 숫자가 있는지, 세로에 겹치는 숫자가 있는지, 3X3크기의 박스에 겹치는 숫자가 있는지를 검사해주면 된다. 모든 조건을 통과한 숫자들이 유망한 노드가 되는 것이다. 주의할 점은 여기서 유망한 노드는 반드시 1개라는 보장은 없다. 여기까지의 생각으로 코딩을 해 본 결과 예제 입력으로 주어진 스도쿠판은 성공적으로 출력이 되었다. 그러나 오답처리를 받아 별도의 반례가 있나 하고 검색을 통해 알아보니, 모든 스도쿠 판이 0으로 채워진 경우가 있었다. 이에 대한 내용은 코드를 통해 자세히 서술하겠다.
-해법
우선 스도쿠판은 누가봐도 2차원 배열로 구현해야 한다. N-Queen 문제처럼 한 행이나 열에 하나의 퀸만이 오는 것이 아니기 때문이다. 2차원 배열로 구현 후 입력을 받아 저장하고, 한 번 탐색을 통해 현재 스도쿠판의 빈칸인 행, 열 좌표를 객체화하여 ArrayList에 별도로 저장해 둔다. 이런 방식을 사용하는 이유는 재귀 호출을 반복할 때마다 스도쿠 판에서 빈칸을 찾는 방식을 사용하게 되면 당연하게도 시간제 한인 1초를 넘기게 될 것이다. 그렇기 때문에 미리 빈 칸을 저장해 별도의 배열 형태로 저장해 두면 해당 배열에 저장되어 있는 행, 열 값만을 처리해주면 된다.
이후 DFS를 수행 할 메서드를 하나 생성한 후, 앞서 저장해 둔 ArrayList와 각 ArrayList에 저장되어 있는 객체를 참조할 인덱스 값을 넘겨준다. (이 부분은 개인 취향 차이이므로 변형해도 상관은 없다.) 재귀 호출을 반복할 것이므로 당연히 종료부를 우선적으로 선언해준다. 필자의 경우는 인덱스 값을 넘겨주어 Index == ArrayList.size()의 상태에서 종료되는 형태를 이용했다.
이제 만들어진 DFS메서드에서 1부터 9까지의 숫자의 유망성을 테스트해야 한다. 그러기 위해선 별도의 체크 메서드를 구현해야 하는데, 필자는 가로 검사 메서드, 세로 검사 메서드, 3X3 검사 메서드로 3가지로 나누어 구현하였다. (이 부분 역시 취향 차이이다. 다른 분들의 경우 하나의 체크 메서드에서 모든 것을 처리하는 방식을 사용하기도 했다.) 각 메서드의 인자로는 현재 빈칸의 행, 열 좌표 정보와 유망성 검사를 위한 정수를 전달한다. 주의할 점은 1부터 9까지의 유망성 검사를 통했는데도 다음 인덱스로 넘어가지 못하는 경우(예를 들어, 하나의 빈칸에 9를 채운 후 다음 인덱스로 넘어갔을 때 1부터 9까지의 유망성검사를 통과하지 못한 경우 DFS메서드가 종료되어 돌아오면 9로 채워졌던 빈칸을 다시 0으로 만들어주는 작업이 꼭 필요하다.) 자세한 부분은 코드를 보면 이해가 될 것이다.
마지막으로 종료부에 도달했을 때에 주의해야 할 점은 문제에 언급했듯이, 여러 가지 경우의 스도쿠 판이 생성될 수 있을 경우 하나의 경우만 출력하는 것이다. 실제로 모든 스도쿠 판이 0으로 채워진 경우 아래와 같이 여러 경우의 스도쿠 판이 굉장히 많이 반복된다. 그렇기 때문에 최초에 첫 번째 스도쿠 판이 완성될 경우 프로그램 자체를 종료시켜 출력을 완료하는 것이 필요하다.
이제 코드를 보자.
import java.util.*;
class xy{ // 입력 된 스도쿠 판의 빈 칸의 행, 열 정보를 저장 할 클래스이다.
int x;
int y;
public xy(int x,int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int check[][] = new int[9][9]; // 9X9 크기의 스도쿠 판을 생성한다.
// 빈 칸의 정보를 가지고 있는 객체를 저장 할 ArrayList이다.
static ArrayList<xy> arrayList = new ArrayList<>();
//DFS를 수행 할 메소드이다. ArrayList와 인덱스 값을 인자로 전달받는다.
static void dfs(ArrayList<xy> arr,int idx) {
if(idx == arrayList.size()) { // 재귀호출 종료 부
for(int i=0;i<9;i++) {
for(int j=0;j<9;j++) {
System.out.print(check[i][j]+" "); // 스도쿠 판 출력
}
System.out.println("");
}
System.exit(0); // 여러가지의 스도쿠 판을 출력하지 않게 프로그램 종료
}
for(int i=1;i<10;i++) { // 1~9 까지 적합한지 유망성 검사하기 위한 반복
// 유망한 숫자를 고르기 위해 3가지 체크 메소드에 전달하여 검사
if(checkRow(arr,idx,i)==true && checkCol(arr,idx,i)==true && checkBox(arr,idx,i)==true) {
check[arr.get(idx).x][arr.get(idx).y] = i;
dfs(arr,idx+1);
}
// i가 9인채로 반복문이 종료되게 되면 이전에 저장되었던 번호를 지운 후 새로운 스도쿠 판을 생성
if(i==9)
check[arr.get(idx).x][arr.get(idx).y] = 0;
}
}
// 스도쿠에서 빈칸이 포함되어 있는 가로행에 중복검사
static boolean checkRow(ArrayList<xy> arr,int idx,int pro) {
for(int i=0;i<9;i++) { // 가로행의 0~8번 인덱스를 검사
if(arr.get(idx).y == i) continue; // 빈칸의 열은 건너뛴다.
// 후보로 전달 된 정수가 이미 스도쿠 판에 존재하는 숫자와 일치하면
// 유망하지 않은 정수이므로 false 리턴
if( check[arr.get(idx).x][i] == pro) return false;
}
return true;
}
// 스도쿠에서 빈칸이 포함되어 있는 세로열에 중복검사
static boolean checkCol(ArrayList<xy> arr,int idx,int pro) {
for(int i=0;i<9;i++) { // 세로 열의 0~8번 인덱스를 검사
if(arr.get(idx).x == i) continue; // 빈칸의 행은 건너뛴다.
// 후보로 전달 된 정수가 이미 스도쿠 판에 존재하는 숫자와 일치하면
// 유망하지 않은 정수이므로 false 리턴
if(check[i][arr.get(idx).y] == pro) return false;
}
return true;
}
// 스도쿠에서 빈칸이 포함되어 있는 3x3박스의 중복검사
static boolean checkBox(ArrayList<xy> arr,int idx,int pro) {
// (0,0)이 빈칸인 경우, (0,0) ~ (2,2)를 검사해야 한다.
// (1,4)가 빈칸인 경우, (0,3) ~ (2,5)를 검사해야 한다.
// 각 좌표를 3으로 나눠 준 후 *3을 해주면 해당 좌표가 속한 박스의 시작점이 나온다.
int a = arr.get(idx).x/3;
int b = arr.get(idx).y/3;
a*=3;
b*=3;
// 3x3크기의 박스이므로 시작점으로 부터 +3보다 작은 경우만을 반복
for(int i=a;i<a+3;i++) {
for(int j=b;j<b+3;j++) {
// 빈 칸의 좌표는 스킵한다.
if(i == arr.get(idx).x && j == arr.get(idx).y) continue;
// 후보로 전달 된 정수가 이미 스도쿠 판에 존재하는 숫자와 일치하면
// 유망하지 않은 정수이므로 false 리턴
if(check[i][j]!=0 &&check[i][j] == pro) return false;
}
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
for(int i=0;i<9;i++) { // 스도쿠 입력 부
for(int j=0;j<9;j++) {
check[i][j] = sc.nextInt();
}
}
for(int i=0;i<9;i++) { // 스도쿠 빈칸을 ArrayList에 저장
for(int j=0;j<9;j++) {
if(check[i][j]==0){
arrayList.add(new xy(i,j));
}
}
}
dfs(arrayList,0); //ArrayList와 함께 0번째 인덱스부터 스도쿠 판을 채워간다.
}
}
풀이는 이전의 풀이와 같지만, 코드 자체는 좀 더 간결해졌다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
class Dot{ // 빈 스도쿠판의 좌표가 저장 될 클래스
int x;
int y;
public Dot(int x,int y) {
this.x = x;
this.y = y;
}
}
class Main {
static BufferedReader br;
static BufferedWriter bw;
// 백트래킹을 위한 유망성 검사 메소드
static boolean isPossible(int[][]a,int x,int y,int n) {
// 같은 행, 열에 겹치는 값이 있는지 확인
for(int i=0;i<9;i++) {
if(a[x][i] == n) {
return false;
}
if(a[i][y] == n) {
return false;
}
}
// 3x3 크기의 박스의 시작점
int three_x = (x/3)*3;
int three_y = (y/3)*3;
// 박스 안에 겹치는 값이 있는지 확인
for(int i = three_x;i<three_x+3;i++) {
for(int j = three_y;j<three_y+3;j++) {
if(a[i][j] == n)
return false;
}
}
// 모든 유망성 검사가 통과되면 true를 반환한다.
return true;
}
// DFS 메소드
static void dfs(int[][] a, ArrayList<Dot> arr,int idx) throws IOException {
// 인덱스 값이 ArrayList의 size와 같아지면 스도쿠판 출력 후 종료.
if(idx == arr.size()) {
for(int i = 0;i<a.length;i++) {
for(int j=0;j <a.length;j++) {
bw.write(String.valueOf(a[i][j])+" ");
}
bw.newLine();
}
bw.flush();
bw.close();
br.close();
// 스도쿠판의 다양한 경우의 수 중 첫 번째 경우만 출력하기 위해 출력 후 프로그램을 죽인다.
System.exit(0);
}
// ArrayList에 저장된 빈 스도쿠판 좌표 객체
Dot d = arr.get(idx);
// 1~9까지 유망성 검사를 위해 인자로 전달.
for(int i=1;i<=9;i++) {
if(isPossible(a,d.x,d.y,i)) {
// 통과 시 해당 값을 저장
a[d.x][d.y] = i;
// 다음 빈 스도쿠판으로 이동
dfs(a,arr,idx+1);
// 다음 빈 스도쿠판에서 1~9의 값이 유망성검사를 통과하지 못하면 다시 값을 0으로
a[d.x][d.y] = 0;
}
}
}
public static void main(String[] args) throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
ArrayList<Dot> arr = new ArrayList<>();
int a[][] = new int[9][9];
for(int i=0;i<a.length;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<a[i].length;j++) {
a[i][j] = Integer.parseInt(st.nextToken());
// 데이터 입력 과정에서 빈 스도쿠판의 좌표를 ArrayList에 저장
if(a[i][j] == 0) {
arr.add(new Dot(i,j));
}
}
}
// 스도쿠판,ArrayList,참조 인덱스를 인자로 넘겨준다.
dfs(a,arr,0);
}
}