백준 2239번 스도쿠

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

public class Sudoku {
    static int[][] map;
    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++) {
            String str = br.readLine();
            for (int j = 0; j < 9; j++) {
                map[i][j] = str.charAt(j)-'0';
            }
        }
        dfs(0,0);

    }
    public static void dfs(int row, int col){
        if(row==9){
            StringBuilder sb = new StringBuilder();
            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(col==9){
            dfs(row+1,0);
            return;
        }
        if(map[row][col]!=0){
            dfs(row,col+1);
        }
        else if(map[row][col]==0){
            for (int i = 1; i <= 9; i++) {//들어갈 숫자 완전탐색
                boolean rowflag = false;
                for (int j = 0; j < 9; j++) {//중복확인
                    if(map[row][j] == i){
                        rowflag = true;
                        break;
                    }
                }
                boolean colflag = false;
                for (int j = 0; j < 9; j++) {
                    if(map[j][col] == i){
                        colflag = true;
                        break;
                    }
                }
                boolean squareflag = false;
                squareflag = squareCheck(row,col,i);
                if(!rowflag&&!colflag&&!squareflag){
                    map[row][col] = i;
                    dfs(row,col+1);
                    map[row][col] = 0;
                }
            }
        }
    }
    public static boolean squareCheck(int row,int col,int num){
        if(row<3){
            row = 0;
        }
        else if(row<6){
            row = 3;
        } else if (row <9) {
            row = 6;
        }
        if(col<3){
            col = 0;
        }
        else if(col<6){
            col = 3;
        }
        else if(col<9){
            col = 6;
        }
        for (int i = row; i <row+3; i++) {
            for (int j = col; j < col+3; j++) {
                if(map[i][j] == num){
                    return true;
                }
            }
        }
        return false;
    }
}

풀이방법

전체적인 풀이의 설계는 완전탐색을 바탕으로 첫번째 열부터 열을 하나씩 늘려가며 dfs탐색을 수행한다.
마지막열에서는 행을 하나 늘려서 dfs탐색을 해주고, 마지막 행에 도착하면 스도쿠를 끝낸다.

1. map에 숫자가 써있다면, 다음 열을 탐색한다.
2. map이 0이라면, 그 자리에 1부터 9까지 하나씩 넣어본다.
   단, 열중복, 행중복, 사각형 중복을 확인해서 모두 중복이 없을때만, 넣어주고, 다음 열 탐색을 시작한다.
3. 스도쿠에 숫자를 채워 넣다가, 일정 시점에서 어떠한 숫자도 들어갈 수 없다면, 다시 되돌아 가서 다른 숫자를 채워 넣어야 한다.(백트래킹)
   이때, 이미 map[row][col] = i; 를 통해 값을 넣어 줬기 때문에,
   if(map[row][col]!=0) 조건식에 걸리게 되어 1번 조건이 실행된다.
   따라서 다시 되돌아 갈때는 map[row][col] = 0;을 통해 원상복귀를 시켜준다.
4. 이후 row==9가 되는 시점이 오면 StringBuilder를 통해 출력해주고, 시스템을 끝낸다.

후기

1. 전체적인 풀이의 설계를 구현
2. 내부에 백트래킹

2가지가 핵심이었고, 2번에서 헤매긴 했지만, 구현,dfs,백트래킹 3가지의 알고리즘 실력을 늘릴 수 있었던 좋은 문제였다.
나중에 다시 풀어봐야겠다.