[BOJ/백준] 2239 스도쿠

def dfs(cnt):
    if cnt == 81:
        for row in sdoku:
            print(''.join(list(map(str,row))))
        exit()
    else:
        x = cnt//9
        y = cnt%9
        square = (x//3)*3 + y//3
        if sdoku[x][y] == 0:
            for num in range(1,10):
                if not (column_check[y][num] or row_check[x][num] or square_check[square][num]):
                    column_check[y][num] = True
                    row_check[x][num] = True
                    square_check[square][num] = True
                    sdoku[x][y] = num
                    dfs(cnt+1)
                    sdoku[x][y] = 0
                    column_check[y][num] = False
                    row_check[x][num] = False
                    square_check[square][num] = False


        else:
            dfs(cnt+1)



sdoku = []

column_check = [[False for _ in range(10)] for _ in range(9)]
row_check = [[False for _ in range(10)] for _ in range(9)]
square_check =[[False for _ in range(10)] for _ in range(9)]
for x in range(9):
    temp = list(map(int,list(input())))
    for y in range(9):
        if temp[y] != 0:
            square = (x//3)*3 + y//3
            column_check[y][temp[y]] = True
            row_check[x][temp[y]] = True
            square_check[square][temp[y]] = True
    sdoku.append(temp)


dfs(0)

 

 

스도쿠의 특성을 활용해서 하면 된다.

 

먼저 각 열, 각 행, 3*3 사각형의 숫자를 얼만큼 사용했는지를 CHECK 해주는 리스트를 만들어준다.

 

여기서 square 넘버를 부여하는 방식은 (x//3)*3 + (y//3)으로 해서, 가장 위에서 부터 

 

 

0 1 2

3 4 5

6 7 8

 

로 구분이 가능하게 해줬다.

 

그리고 dfs를 활용해서, cnt는 전체 칸의 갯수를 뜻하면서, 좌표를 뜻하도록 했다. 해당 좌표에서 비어있으면,

 

숫자를 하나씩 넣어가면서 백트래킹을 해줬다.

 

 

그리고 마지막에 도착하면, 현재 스도쿠를 출력해주고, 함수를 종료시켜줬다.

 

 

가장 앞에서부터 하나하나씩 채워나가는 것이기때문에, 가장 먼저 완료되는것이 사전순으로 가장 빠른 스도쿠가 된다.