백준 2239번 (java) DFS, 백트래킹

---

백준 2239번: 스도쿠 JAVA

---

관찰

스도쿠를 만들때 가로검사, 세로검사, 사각형 검사가 필요하다 일단
그리고 사전식으로 앞서는 것을 출력해야 한다 0,0 0,1 0,2 ,,, 8,7 8,8 이런 식으로 탐색 + 작은 수 부터 대입을 해야한다
스도쿠의 특성상 그냥 대입하면 나중에 넣은 값 때문에 못 넣을 수 있다 최적의 조합을 찾아야 한다!
완탐을 해서 백트래킹으로 모든 경우의 수를 탐색하여 수를 다 채웠다면 탈출해보자 9*9니깐 완탐 가능할 듯...?

---

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[][] map;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        map = new int[9][9];
        for(int i=0;i<9;i++) {
            char[] tmp = br.readLine().toCharArray();
            for(int j=0;j<9;j++) {
                map[i][j] = tmp[j] - '0';
            }
        }
        dfs(0,0);
    }

    private static void dfs(int r, int c) {
        if(r >= 9) { // 탈출!
            for(int i=0;i<9;i++) {
                for(int j=0;j<9;j++) {
                    sb.append(map[i][j]);
                }
                sb.append("\n");
            }
            System.out.println(sb);
            System.exit(0);
        }
        if(c >= 9) { // 한 줄 끝!
            dfs(r+1,0);
            return;
        }

        if(map[r][c] == 0) {
            for(int k=1;k<=9;k++) {
                if(!checkBox(r,c,k)) continue;
                if(!checkRow(r,c,k)) continue;
                if(!checkCol(r,c,k)) continue;
                map[r][c] = k;
                //System.out.println("r = " + r + ", c = " + c + ", map = " + map[r][c]);
                dfs(r,c+1);
                map[r][c] = 0; // 백 트래킹 
            }
        }
        else{
            dfs(r,c+1);
        }
    }
    // 사각형 탐색
    private static boolean checkBox(int r,int c,int num) {
        int sr = 0;
        int sc = 0;

        sr += (r/3)*3;
        sc += (c/3)*3;

        for(int i=0;i<3;i++) {
            for(int j=0;j<3;j++) {
                if(map[sr+i][sc+j] == num) return false;
            }
        }

        return true;
    }
    // 가로 탐색
    private static boolean checkCol(int r,int c,int num) {
        int ec = c-1;
        int nc = c+1;
        while(!isOut(r,ec)) {
            if(map[r][ec] == num) return false;
            ec--;
        }
        while(!isOut(r,nc)) {
            if(map[r][nc] == num) return false;
            nc++;
        }
        return true;
    }
    // 세로 탐색
    private static boolean checkRow(int r,int c,int num) {
        int er = r-1;
        int nr = r+1;
        while(!isOut(er,c)) {
            if(map[er][c] == num) return false;
            er--;
        }
        while(!isOut(nr,c)) {
            if(map[nr][c] == num) return false;
            nr++;
        }
        return true;
    }
    
    private static boolean isOut(int i, int j) {
        return i<0 || j<0 || i>= 9 || j >= 9;
    }
}

---

풀이

dfs를 적용시켜야 하는데 순서가 일반 문제와 달라서 기저 조건 두개를 활용해서 구현하였다.
그리고 사각형을 탐색하는 데 sr += (r/3)*3; 이 방식으로 시작점을 잡아주는 트릭!
백트래킹을 적용해주고 완전히 다 채운 순간에 값을 담는다!

---

느낀점

사실 처음 풀 때 시간초과가 났다 관찰해보니 이 dfs 코드는 끝나는 기저조건을 달성해서 출력을 담아도 끝나지 않는다는 사실을 알게 되었고 이 시간을 줄여주기 위해서 dfs 함수 안에서 출력후 시스템 종료를 해주어서 풀 수 있었다!

dfs 구현,작동에 대한 이해 + 백트래킹에 대한 이해 + 구현능력 이 필요한 문제였고 재밌는 문제였다!