백준(BOJ) 2580 : 스도쿠 (JAVA)

문제링크 : https://www.acmicpc.net/problem/2580

2580번: 스도쿠

단순하게만 생각한다면, '빈 칸이 포함되는 가로줄, 세로줄, 9개의 네모 칸 안의 수를 다 비교해서, 빈칸에 넣을 수 있는 수를 넣으면 되는 거 아닌가?'라고 생각할 수 있다. 이것도 틀린 말은 아니나 소싯적(?) 스도쿠를 조금이라도 해본 사람은 이게 그렇게 간단한 문제는 아니라는 걸 알 것이다. 다 비교해봐도 빈 칸 안에 넣을 수 있는 수가 1개가 넘는 경우가 많기 때문이다. 심지어 이 문제에는 '판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.'라는 조건이 있다. 그 말은 81개의 모든 칸이 0으로 주어진다고 해도 답이 나와야한다는 얘기다. 뭔가 완전 탐색의 냄새(?)가 나지 않는가?ㅋㅋ 풀이에 대한 설명을 시작하겠다. 일단 이 풀이는 DFS 백트래킹이며, 자세한 건 코드를 보고 설명하는 편이 나을 듯하다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
    private static boolean finished = false;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] puzzle = new int[9][9];
        List<Point> zeroList = new ArrayList<Point>();
        
        for(int i = 0; i < 9; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for(int j = 0; j < 9; j++) {
                puzzle[i][j] = Integer.parseInt(st.nextToken());
                
                if(puzzle[i][j] == 0) {
                    zeroList.add(new Point(i, j));
                }
            }
        }
        
        if(zeroList.size() > 0) {
            dfs(zeroList.get(0), puzzle, zeroList, 0);
        } else {
            printPuzzle(puzzle);
        }    
    }
 
    private static void dfs(Point point, int[][] puzzle, List<Point> zeroList, int depth) {
        if(finished) {
            return;
        }
        
        boolean[] checked = getCandidates(puzzle, point);
        
        for(int k = 1; k <= 9; k++) {
            if(!checked[k]) {
                int i = point.getI();
                int j = point.getJ();
                
                puzzle[i][j] = k;
                
                if(depth == zeroList.size() - 1) {
                    printPuzzle(puzzle);
                    finished = true;
                    return;
                }
                
                dfs(zeroList.get(depth + 1), puzzle, zeroList, depth + 1);            
                puzzle[i][j] = 0;
            }
        }
    }
 
    private static void printPuzzle(int[][] puzzle) {
        StringBuffer sb = new StringBuffer();
        
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                sb.append(puzzle[i][j] + " ");
            }
            
            sb.append("\n");
        }
        
        System.out.println(sb);
    }
    
    private static boolean[] getCandidates(int[][] puzzle, Point point) {
        int i = point.getI();
        int j = point.getJ();
        boolean[] checked = new boolean[10];
        
        for(int k = 0; k < 9; k++) {
            checked[puzzle[i][k]] = true;
        }
        
        for(int k = 0; k < 9; k++) {
            checked[puzzle[k][j]] = true;
        }
        
        int sI = i / 3 * 3;
        int sJ = j / 3 * 3;
        
        for(int k = sI; k < sI + 3; k++) {
            for(int h = sJ; h < sJ + 3; h++) {
                checked[puzzle[k][h]] = true;
            }
        }
        
        return checked;
    }
    
    private static class Point {
        private int i;
        private int j;
        
        public Point(int i, int j) {
            this.i = i;
            this.j = j;
        }
 
        public int getI() {
            return i;
        }
 
        public int getJ() {
            return j;
        }    
    }
}

1. 빈 칸의 위치를 모두 List에 저장한다.

2. 첫번째 빈 칸에 들어갈 수 있는 모든 수를 구한 후, 하나씩 넣은 후, DFS로 다음 빈 칸으로 이동한다.

3. 다음 빈 칸에 대해서도 동일하게(재귀함수) 들어갈 수 있는 모든 수를 구한 후, 하나씩 넣고 다음 칸으로 이동한다.

4. 만약 List에 저장되있는 모든 빈 칸에 대해 숫자가 채워졌다면 함수 실행을 멈추고 값을 출력한다.

5. 만약 현재 넣어본 수가 스도쿠의 조건을 만족할 수 없는 수라면, DFS를 도는 어느 순간, 해당 빈 칸에 들어갈 수 있는 수가 0개로 나올 것이고 해당 조건은 모든 빈 칸을 채울 수 없을 것이다. 해당 depth를 충족시킬 수 없을 것이다. 

6. 아까 빈 칸에 들어갈 수 있는 여러가지 수 중 하나를 일단 넣어봤다. 다른 경우의 수도 알아보려면 아까 수를 넣기 이전 상태로 초기화가 되어야한다. 칸을 다시 빈 칸(0)으로 초기화해준다.(백트래킹)

 

근데 상위권 풀이에 비해 실행시간이 다소 길다...-_- 상위권 풀이를 살펴보니, 굳이 빈칸에 넣을 수 있는 수를 매번 구할 필요가 없다라는 걸 깨달았다. 코드는 아래와 같다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
    private static boolean finished = false;
    private static boolean[][] checkI = new boolean[9][10];
    private static boolean[][] checkJ = new boolean[9][10];
    private static boolean[][][] checkBox = new boolean[3][3][10];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] puzzle = new int[9][9];
        List<Point> zeroList = new ArrayList<Point>();
        
        for(int i = 0; i < 9; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for(int j = 0; j < 9; j++) {
                puzzle[i][j] = Integer.parseInt(st.nextToken());
                
                if(puzzle[i][j] == 0) {
                    zeroList.add(new Point(i, j));
                } else {
                    checkI[i][puzzle[i][j]] = true;
                    checkJ[j][puzzle[i][j]] = true;
                    checkBox[i / 3][j / 3][puzzle[i][j]] = true;
                }
            }
        }
        
        if(zeroList.size() > 0) {
            dfs(zeroList.get(0), puzzle, zeroList, 0);
        } else {
            printPuzzle(puzzle);
        }    
    }
 
    private static void dfs(Point point, int[][] puzzle, List<Point> zeroList, int depth) {
        if(finished) {
            return;
        }
        
        int i = point.getI();
        int j = point.getJ();
        
        for(int k = 1; k <= 9; k++) {
            if(!checkI[i][k] && !checkJ[j][k] && !checkBox[i / 3][j / 3][k]) {
                
                puzzle[i][j] = k;
                checkI[i][k] = true;
                checkJ[j][k] = true;
                checkBox[i / 3][j / 3][k] = true;
                
                if(depth == zeroList.size() - 1) {
                    printPuzzle(puzzle);
                    finished = true;
                    return;
                }
                
                dfs(zeroList.get(depth + 1), puzzle, zeroList, depth + 1);            
                puzzle[i][j] = 0;
                checkI[i][k] = false;
                checkJ[j][k] = false;
                checkBox[i / 3][j / 3][k] = false;
            }
        }
    }
 
    private static void printPuzzle(int[][] puzzle) {
        StringBuffer sb = new StringBuffer();
        
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                sb.append(puzzle[i][j] + " ");
            }
            
            sb.append("\n");
        }
        
        System.out.println(sb);
    }
 
    private static class Point {
        private int i;
        private int j;
        
        public Point(int i, int j) {
            this.i = i;
            this.j = j;
        }
 
        public int getI() {
            return i;
        }
 
        public int getJ() {
            return j;
        }    
    }
}