[백준] 2239 : 스도쿠 - Python

문제

스도쿠 채우기 문제.

내 코드

import sys
from collections import deque

sys.stdin = open("input.txt", "rt")

g = [list(map(int, input())) for _ in range(9)]
# ! 9x9 스도쿠

# ! 좋은 방향 : 일단 0인 좌표를 미리 넣어둔다
dq = deque()
for i in range(9):
    for j in range(9):
        if g[i][j] == 0:
            dq.append((i,j)) # ! 해당 좌표 넣어둠

x,y = dq[0] # ! 시작 좌표
def check_row(x,y,val):
    # ! 해당 행 검사 -> 행 고정, 열 변수
    for i in range(9):
        if g[x][i] == val: # ! 이미 존재
            return False
    else:
        return True
def check_col(x,y,val):
    # ! 해당 열 검사 -> 열 고정, 행 변수
    for i in range(9):
        if g[i][y] == val: # ! 이미 존재
            return False
    else:
        return True

def check(x,y,val): # ! 현재 좌표가 속한 미니 박스 확인
    dx = (x // 3) * 3
    dy = (y // 3) * 3
    for i in range(dx,dx+3):
        for j in range(dy,dy+3):
            if g[i][j] == val:
                return False
    return True

flag = True
def DFS(L):
    global flag
    if not flag: return
    if L == len(dq):
        flag = False
    else:
        x,y = dq[L]
        for i in range(10):
            if check(x,y,i) and check_row(x,y,i) and check_col(x,y,i):
                g[x][y] = i
                DFS(L+1)
                if not flag: return # ! 다 돌았으면 원상복구 안함.
                g[x][y] = 0


DFS(0)
for i in range(9):
    for j in range(9):
        print(g[i][j], end = "")
    print()

코멘트

해당 문제는 처음에 생각했던 "진짜 처음부터 다 채워봐야 하나?"를 그대로 구현하면 된다.
근데, 작은 경우부터 넣어야 하므로 하나씩 넣어보면서 안되는 경우 백트랙킹. (원상복구)
다시 그곳에서부터 시작.

처음에 값이 0인 좌표들을 모두 따로 리스트에 저장해두기
이제 첫 0인 좌표부터 DFS 시작. 하나씩 넣어보면서 row, col, 3x3에서 모두 가능한지 판별. 계속 모두 확인하면 된다.

종료조건 : L == len(dq) -> 즉 0의 개수를 모두 확인한 순간 모두 끝나야만 한다.
기본 적인 DFS 틀에서 빈 자리에서 1~9까지 숫자 중 가능한 숫자를 확인하면서 체킹하면 된다는 뜻!

빈 칸의 모든 좌표들에 숫자를 채울 수 있을 때까지 과정 반복.

모두 사용하지 않는 숫자 고르고 체킹 후에 다음 좌표로 이동하는게 핵심. 만약 안된다면 백.

java 코드

import java.awt.*;
import java.io.*;
import java.util.*;
import java.util.List;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[][] g;
    private static class Point{
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static List<Point> blank = new ArrayList<>();
    public static void main(String[] args) throws IOException {

        g = new int[9][9];
        for (int i = 0; i < 9; i++) {
            String data = br.readLine();
            for (int j = 0; j < 9; j++) {
                g[i][j] = data.charAt(j) - '0';
            }
        }

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (g[i][j] == 0) {
                    blank.add(new Point(i, j));
                }
            }
        }

        DFS(0);

    }

    public static void DFS(int L){
        if (L == blank.size()) { // ! 모두 확인
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(g[i][j]);
                }
                System.out.println();
            }
            System.exit(0);
        } else {
            Point now = blank.get(L);
            int x = now.x;
            int y = now.y;
            for (int i = 1; i <= 9; i++) {
                // ! x,y 자리에 어울리는지 판단
                if(check_box(x,y,i) && check_row(x,y,i) && check_col(x,y,i)){
                    g[x][y] = i; // ! 해당 값 가능
                    DFS(L+1); // ! 다음으로 가서 다시 확인
                    g[x][y] = 0; // ! 백트랙킹 시 원상 복구
                }
            }
        }
    }

    public static boolean check_row(int x, int y, int val) {
        // ! 행 체크 -> 행 고정 열 변수
        for (int i = 0; i < 9; i++) {
            if(g[x][i] == val) return false;
        }
        return true;
    }

    public static boolean check_col(int x, int y, int val) {
        // ! 열 체크 -> 열 고정 행 변수
        for (int i = 0; i < 9; i++) {
            if(g[i][y] == val) return false;
        }
        return true;
    }

    public static  boolean check_box(int x, int y, int val){
        // ! 3x3 확인
        int dx = (x/3) * 3;
        int dy = (y/3) * 3;
        for (int i = dx; i < dx + 3; i++) {
            for (int j = dy; j < dy + 3; j++) {
                if(g[i][j] == val) return false;
            }
        }
        return true;
    }

}