백준 2580번 - 스도쿠 (Java)

https://www.acmicpc.net/problem/2580

2580번: 스도쿠

코드 :

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static final int SUDOKU_BOARD_SIZE = 9;
    static int[][] board = new int[SUDOKU_BOARD_SIZE][SUDOKU_BOARD_SIZE];
    static StringBuilder answer = new StringBuilder();


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;



        for (int i = 0; i < SUDOKU_BOARD_SIZE; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < SUDOKU_BOARD_SIZE; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dfs(0,0);
    }

    private static void dfs(int row, int col) {

        /*
         마지막 열일 경우 다음 행 첫번째부터 시작
         재귀하지 않고 인수를 갱신하면, 아래쪽 코드에는 적용이 되지 않는다.
         */
        if (col == 9) {
            dfs(row + 1, 0);
            return;
        }

        // 완성 시 정답 출력
        if (row == 9) {
            for (int i = 0; i < SUDOKU_BOARD_SIZE; i++) {
                for (int j = 0; j < SUDOKU_BOARD_SIZE; j++) {
                    answer.append(board[i][j]).append(" ");
                }
                answer.append("\n");
            }
            System.out.print(answer.toString().trim());
            System.exit(0);
        }


        if (board[row][col] == 0) {
            for (int i = 1; i <= 9; i++) {
                if (isPossible(row, col, i)) {
                    board[row][col] = i;
                    dfs(row, col + 1);
                }
            }
            board[row][col] = 0;
            return;
        }

        dfs(row, col + 1);
    }

    private static boolean isPossible(int row ,int col, int num) {
    
    	// 행(가로) 순회하며 검사
        for (int i = 0; i < SUDOKU_BOARD_SIZE; i++) {
            if (board[row][i] == num) {
                return false;
            }
        }

        // 열(세로) 순회하며 검사
        for (int i = 0; i < SUDOKU_BOARD_SIZE; i++) {
            if (board[i][col] == num) {
                return false;
            }
        }

        // 3x3 사각형 순회하며 검사
        row = (row / 3) * 3;
        col = (col / 3) * 3;

        for (int k = row; k < row + 3; k++) {
            for (int l = col; l < col + 3; l++) {
                if (board[k][l] == num) {
                    return false;
                }
            }
        }
        return true;
    }

}

풀이 :

https://st-lab.tistory.com/119

이분 덕분에 숨통이 트였다. 처음에 열심히 풀었는데 시간초과가 나서 좌절했다가 보고 다시 풀었다. 틀에 박힌 방식과 조금 달랐을 뿐인데 당황스러웠다.

 

 

추가 1

처음에 해당 부분이 헷갈렸다.

 

빨간 네모에 도달하는 경우를 생각해보면,

 

•  조건문(isPossible)이 실행된 경우  : 재귀했다가 돌아온 경우는 다 채우기를 실패했다는 것이다. 해당 보드에 시도했던 숫자를 지운다.
•  조건문이 실행되지 않음 : 어짜피 0이므로 상관 없다.

어찌되었든, 현재 탐색하는 스도쿠 위치의 값이 0인데, 해당 0 을 바꾸지 못하면 더 탐색해도 의미가 없기때문에 종료시켜버리는 것이다. 그리고 애초에 0이 아니라면, 다음으로 넘어가야하기 때문에 마지막에 dfs를 재귀호출 한다.

 

 

추가 2

조건문과 함께 재귀하는 부분을 생각해보면, 스도쿠를 채울 때 여러 수가 채워지는 경우가 있었다.

0	3	5	6	7	8	0	1	2
1	0	8
2	6	7
3
0
5
6
7
8

위 코드에서 row = 0, col = 0 인 상태라고 가정하자. 탐색하는 모양에 대한 숫자만 써놓은 상태다.

 

우선 board[0][0]은 0이기(0을 만났기) 때문에 "if (board[row][col] == 0)" 을 통과한다. 그 다음 for문을 순회하면서 들어갈 수 있는 숫자를 찾는데, 문제는 첫번째 0에 4도 들어갈 수 있고, 9도 들어갈 수 있다.

 

그렇다면  board[0][0]에 3을 쓴 경우가 먼저 dfs를 한다. 그 다음 4를 쓴 경우도 dfs를 하는 것이다. 3을 쓴 경우에 대한 탐색이 실패하면 결국 돌아오게 되며, for문으로 인해 4를 쓴 경우도 탐색하게 된다.