백준 2239 스도쿠 ( java )

전형적인 백트래킹 문제라는데 사실 아직 문제를 보면 딱 ㅇㅇ로 푸는거구나~ 하는 생각이 안드는 경우가 많다.

왜 백트래킹을 쓰는지에 대해 생각을 해보니

1. 일단 완탐을 해야 하는거 같지만

2. 한번 완료하면 더이상 탐색을 할 필요가 없음 (많은 정답중에 사전식으로 하나만 출력하기 때문)

3. 따라서 해당 경우를 가지치기를 하기 위해서 -> 백트래킹 사용 

이런식으로 생각해야 하지 않을까 싶다.

 

개인적으로 백트래킹이라는 냄새를 맡으면 조금 쉬운 문제가 아닐까..? 싶다

DP를 풀다와서 그런가 실버DP문제보다 골드문제가 더 쉬운건... 기분탓이겠지...

 

풀이과정

- map[9][9]에 스도쿠를 입력 받아준다.

- 모든 칸을 너비기준으로 탐색해야 하기 때문에 DFS가 적합

- dfs는 depth를 기준으로 depth == 81 ( 9 * 9 = 81 이므로) 일때 탐색을 종료

- depth = 현재 위치의 행 x 열 이므로 현재 위치는 (행) depth / 9  , (열) depth % 9 

 

(탐색 과정)

- flag (스도쿠가 완성되면 더이상 진행을 안하기 위한 boolean 변수)

- 현재 위치가 0 인지 체크 ( 이미 스도쿠가 채워져있다면 다음 탐색을 진행하면 되기 때문) 

- 숫자 1~9 까지 해당 칸에 넣어보면서 DFS 진행 

  해당 칸에 n이라는 숫자가 들어갈 수 있는지 체크 -> 불가능하면 다음 숫자로 continue

  가능하다면 현재 위치에 n을 넣은 뒤 DFS(depth+1) 진행 

  진행 시킨뒤 또 다른 숫자도 가능한지 확인해야 하기 때문에 현재 위치의 값을 이전상태로 돌려 놓아야한다.

  (이부분을 놓쳐서 조금 고생했다)

 

---

package Baekjoon.Gold;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
/**
 * {@auther} : daeun
 * @since : 2022-04-06
 * link : https://www.acmicpc.net/problem/2239
 * type : 구현, 백트래킹
 * */
public class 백준_G5_스도쿠 {
    static int[][] map = new int[9][9];
    static boolean flag; // 스도쿠가 완성되었는지
    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++) {
            String str = br.readLine();
            for (int j = 0; j < 9; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
        // 사전식 출력 -> 제일 작은 값부터 채워넣자 (1 ~ 9)
        // 백트래킹 조건 -> 이미 스토쿠가 완성되었거나, 같은 수가 가로 , 세로 줄에 존재하거나, 3*3 안에 같은 수가 존재하는 경우
        dfs(0);
        for(int r=0; r<9; r++){
            for(int c=0; c<9; c++){
                sb.append(map[r][c]);
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
    public static void dfs(int depth) {
        if (depth == 81) {    // 9 * 9 = 81칸 -> 0~80까지 돌면 81칸이므로 마지막 호출 depth : 81
            flag = true; // 스도쿠 완성
            return;
        }
        int row = depth / 9; // 행
        int col = depth % 9; // 열
        if(map[row][col] != 0){        // 채워진 곳인지 확인하기 -> 이미 채워진 곳이라면 dfs 탐색 진행
            dfs(depth+1);
        }else{  // 채워야 할 공간이라면
            for(int i=1; i<=9; i++){
                if(!isOk(row,col,i)) continue; // 불가능한 경우 pass
                map[row][col] = i;  // map에 i를 넣은 채로 dfs 진행해보기
                dfs(depth+1);
                if(flag) return; // 스도쿠가 완성되었다면 return(종료)
                map[row][col] = 0;   // 다시 진행해야 하므로 -> map을 이전 상태로 복구시켜놓기
            }
        }
    }
    public static boolean isOk(int row, int col, int n) {
        // 가로줄, 세로줄에 n 이 있는지
        for(int i=0; i<9; i++){
            if(map[row][i] == n) return false;
            if(map[i][col] == n) return false;
        }
        // 3*3 사각형에 n이 있는지
        int sR = row / 3;
        int sC = col / 3;
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                if(map[i+3*sR][j+3*sC] == n) return false;
            }
        }
        return true; // 조건 전부 충족할 경우
    }
}