방과후
ALGORITHM NOTE약 1분

BOJ 2239 - 스도쿠

그냥 스도쿠 풀고 싶어요

#algorithm#boj#gold#implementation#backtracking
아카이브로 돌아가기

문제 링크

문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

풀이

빈 칸을 하나씩 채워 가며 가능한 수를 시도하는 전형적인 백트래킹 문제다. 한 칸에 숫자를 넣을 수 있는지는 같은 행, 같은 열, 같은 3 x 3 칸만 보면 판정할 수 있다.

코드에서는 빈 칸 목록을 모아 두고, 현재 칸에 1부터 9까지 가능한 숫자를 넣어 본다. 조건을 만족하면 다음 칸으로 재귀를 이어 가고, 끝까지 완성되면 그대로 정답을 출력한다.

핵심은 유효성 검사와 되돌리기다.

코드

java
import java.io.*;
import java.util.*;
 
public class Main {
 
    static int[][] sudoku = new int[9][9];
    // 1 : 3x3 사각형, 2 : 가로, 3 : 세로
    static int[] check1 = new int[9];
    static int[] check2 = new int[9];
    static int[] check3 = new int[9];
    static ArrayList<int[]> zeroList = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        for (int i = 0; i < 9; i++) {
            String input = br.readLine();
            for (int j = 0; j < 9; j++) {
                int num = input.charAt(j) - '0';
                sudoku[i][j] = num;
                if (num != 0) {
                    check1[getSquareIdx(i, j)] |= (1 << num);
                    check2[i] |= (1 << num);
                    check3[j] |= (1 << num);
                } else {
                    zeroList.add(new int[]{i, j});
                }
            }
        }
 
        solve(0);
    }
 
    static int getSquareIdx(int x, int y) {
        return (x / 3) * 3 + (y / 3);
    }
 
    static void solve(int depth) {
        if (depth == zeroList.size()) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++)
                    sb.append(sudoku[i][j]);
                sb.append('\n');
            }
 
            System.out.println(sb);
            System.exit(0);
        }
 
        int x = zeroList.get(depth)[0];
        int y = zeroList.get(depth)[1];
 
        for (int i = 1; i <= 9; i++) {
            if ((check1[getSquareIdx(x, y)] & (1 << i)) == 0 &&
                    (check2[x] & (1 << i)) == 0 && (check3[y] & (1 << i)) == 0) {
                check1[getSquareIdx(x, y)] |= (1 << i);
                check2[x] |= (1 << i);
                check3[y] |= (1 << i);
                sudoku[x][y] = i;
 
                solve(depth + 1);
 
                check1[getSquareIdx(x, y)] &= ~(1 << i);
                check2[x] &= ~(1 << i);
                check3[y] &= ~(1 << i);
                sudoku[x][y] = 0;
            }
        }
    }
}

복잡도

  • 시간 복잡도: 빈 칸 수를 EE라 하면 스도쿠 후보를 백트래킹하므로 최악의 경우 O(9E)O(9^E)이다.
  • 공간 복잡도: 보드 크기는 고정이고 재귀 스택만 사용하므로 O(E)O(E)이다.

마무리

스도쿠는 결국 가능한 숫자만 조심해서 넣어 보는 백트래킹이다. 행, 열, 칸 검사만 정확하면 정답은 재귀가 찾아준다.