백준 - 2239,2580번(백트래킹, 스도쿠)

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

2580번: 스도쿠

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

2239번: 스도쿠

 

import sys

arr = []
blank = []

for _ in range(9):
    arr.append(list(map(int,sys.stdin.readline().split())))

for i in range(9):
    for j in range(9):
        if arr[i][j] == 0:
            blank.append([i,j])
            #빈칸만 따로 모아 놓는다.

def check(a, b):
    possible = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    s1 = 0
    s2 = 0

    # row check
    for i in arr[a]:
        if i != 0:
            possible[i - 1] = 0

    # column check
    for i in range(9):
        if arr[i][b] != 0:
            possible[arr[i][b] - 1] = 0

    # 3 by 3 check
    if a >= 0 and a < 3:
        s1 = 0
        if b >= 0 and b < 3:
            s2 = 0
        elif b >= 3 and b < 6:
            s2 = 3
        elif b >= 6 and b < 9:
            s2 = 6

    elif a >= 3 and a < 6:
        s1 = 3
        if b >= 0 and b < 3:
            s2 = 0
        elif b >= 3 and b < 6:
            s2 = 3
        elif b >= 6 and b < 9:
            s2 = 6

    elif a >= 6 and a < 9:
        s1 = 6
        if b >= 0 and b < 3:
            s2 = 0
        elif b >= 3 and b < 6:
            s2 = 3
        elif b >= 6 and b < 9:
            s2 = 6

    for i in range(s1, s1 + 3):
        for j in range(s2, s2 + 3):
            if arr[i][j] != 0:
                possible[arr[i][j] - 1] = 0

    return possible


def DFS(p):
    if len(blank) == p:
        for i in range(9):
            print(*arr[i])
        exit(0)

    x = blank[p][0]
    y = blank[p][1]

    poss = check(x,y)

    for i in poss:
        if i != 0:
            arr[x][y] = i
            DFS(p+1)
            arr[x][y] = 0

DFS(0)

 

핵심은 다음과 같다.

먼저 빈칸을 blank 배열에 따로 모아 놓는다.

가로, 세로, 3x3을 확인해줄 check 함수를 작성한다.

DFS로 탐색한다.

DFS로 탐색할때 blank에 들어 있는 빈칸들만 탐색해준다.

check 배열에서 빈칸에 들어갈 수 있는 숫자를 poss로 return 해준다.

poss에 있는 숫자들중 0이 아닌 숫자들을 arr에 넣으면서 재귀적으로 탐색한다.

만약에 아닐경우 다시 arr [x][y]를 처음의 값으로 바꿔주는 것이 백트래킹의 핵심이다.