[BOJ] 2239:스도쿠

0. 문제

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

2239번: 스도쿠

 

1. 문제분석

- 특정 위치에 1-9 중 하나의 숫자를 넣을 때에 스도쿠의 모든 조건을 만족하는지 여부를 판단해보아야 하고, 조건을 만족하는지 여부는 이전에 선택했던 결과들(현재 이전의 위치 중 비어있는 자리에 수를 넣은 것)이 영향을 미친다는 점에서 backtracking 방식으로 문제를 풀어야 함을 알 수 있다.

- row[i][j], col[i][j], square[i][j]: i번째 행, 열, 3x3 사각형 중 숫자 j가 존재하는지. square의 i는 (x/3)*3 + y/3 의 식을 사용해 계산한다.

 

2. 주의할 점

- square 배열의 첨자를 계산하는 식은 3진법을 생각하면서 유도한다.

- 출력해야 하는 결과는, 조건을 만족하는 81자리 수 중 가장 작은 것이므로, 가장 번호가 낮은 행부터 차근차근 자리에 맞는 숫자를 찾아나가야 한다.

 

3. 소스코드(Java)

// boj 2339 스도쿠
// 백트래킹

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class boj_02339 {
    static int cnt = 0;
    static boolean found = false;
    static int[][] sudoku = new int [9][9];
    static boolean[][] row = new boolean[9][10];
    static boolean[][] col = new boolean[9][10];
    static boolean[][] square = new boolean[9][10];

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] line;
        for (int i = 0; i < 9; ++i) {
            sudoku[i] = new int[9];
            row[i] = new boolean[10];
            col[i] = new boolean[10];
            square[i] = new boolean[10];
        }
        for (int i = 0; i < 9; ++i) {
            line = br.readLine().toCharArray();
            for (int j = 0; j < 9; ++j) {
                int now = line[j] - '0';
                sudoku[i][j] = now;
                if (now > 0) {
                    cnt++;
                    row[i][now] = true;
                    col[j][now] = true;
                    square[(i / 3) * 3 + j / 3][now] = true;
                }
            }
        }
        go(0,0);
    }

    static void go(int x, int y) {
        if (found) return;
        if (cnt >= 81) {
            found = true;
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) sb.append(sudoku[i][j]);
                sb.append('\n');
            }
            System.out.print(sb);
            return;
        }
        int nx, ny;
        if (y + 1 > 8) {
            nx = x + 1;
            ny = 0;
        } else {
            nx = x;
            ny = y + 1;
        }
        if (sudoku[x][y] > 0) {
            go(nx, ny);
        } else {
            for (int i = 1; i <= 9; ++i) {
                if (placeable(x,y,i)) {
                    place(x,y,i);
                    go(nx, ny);
                    displace(x,y,i);
                }
            }
        }
    }

    static boolean placeable (int x, int y, int toPlace) {
        return !row[x][toPlace] && !col[y][toPlace] && !square[(x/3)*3+y/3][toPlace];
    }
    static void place(int x, int y, int toPlace) {
        sudoku[x][y] = toPlace;
        cnt++;
        row[x][toPlace] = true;
        col[y][toPlace] = true;
        square[(x/3)*3+y/3][toPlace] = true;
    }
    static void displace(int x, int y, int toDisplace) {
        sudoku[x][y] = 0;
        cnt--;
        row[x][toDisplace] = false;
        col[y][toDisplace] = false;
        square[(x/3)*3+y/3][toDisplace] = false;
    }
    
}

 

4. 여담

- 다음 위치로 넘어가는 로직을 찾는 데에 생각보다 시간이 오래 걸렸다..ㅠ