[백준] 스도쿠 2239

스도쿠 2239 문제 요약

9x9 스도쿠 퍼즐이 주어졌을 때, 스도쿠 규칙에 맞게 수가 채워지도록 해야한다.

생각

판은 9x9 총 81칸
모든 빈칸이 0이라고 생각했을 때 1~9까지 숫자가 들어갈 수 있고 모든 경우를 탐색하면 $O(9^{81})$이다.
제한 시간에 풀 수 없다고 생각함.
하지만 이건 브루트 포스 방식이고 제약 조건 걸어서 가지치기 되면 속도를 줄일 수 있다고 생각.
빈칸 '0'에 숫자를 하나 넣으면 행, 열, 3x3 판에 다른 숫자를 쓸 수 없기에 선택지가 줄어든다.

풀이 구조

가지치기 위해서 넣을려고 하는 숫자가 괜찮은지 확인해야한다.
숫자를 넣을 때마다 반복문을 돌려 가로, 세로, 3x3에 겹치는 수가 있는지 확인하면 시간초과 날 것.
그래서 숫자 사용했는지 기록하는 배열 3개 구성.

• row[i][num] - i번째 행에 num 있는지
• col[j][num] - j번째 행에 num 있는지
• square[k][num] - k번째 3x3에 num 있는지 => k = (i//3)*3 + (j//3)
  이러면 해당 칸에 num을 넣어도 되는지 O(1)에 확인 가능하다.

판에 '0'인 수를 모아두는 배열을 만들어서 '0' 좌표들 값을 통해 백트래킹으로 수행

결론

1. 빈 칸에 1~9까지 숫자 넣어보기
2. 행, 열, 3x3에 이미 존재하는 숫자라면 가지치기
3. 존재하지 않는 숫자라면 다음 빈 칸으로 넘어가기
4. 모든 빈 칸을 채웠다면 스도쿠 완성, 출력 후 종료

풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# row[i][num] - i번째 행에 num 있는지
# col[j][num] - j번째 행에 num 있는지
# square[k][num] - k번째 3x3에 num 있는지

board = [list(input().rstrip()) for _ in range(9)]
check = []

row = [[False] * 10 for _ in range(9)]
col = [[False] * 10 for _ in range(9)]
square = [[False] * 10 for _ in range(9)]

def func(cnt):
    if cnt == len(check):
        for li in board:
            print("".join(li))

        sys.exit(0)
    
    x, y = check[cnt]
    k = (x // 3) * 3 + (y // 3)

    for number in range(1, 10):
        
        if not row[x][number] and not col[y][number] and not square[k][number]:
            row[x][number] = col[y][number] = square[k][number] = True
            board[x][y] = str(number)

            func(cnt + 1)
            row[x][number] = col[y][number] = square[k][number] = False
            board[x][y] = '0'


for i in range(9):
    for j in range(9):
        num = int(board[i][j])
        if num == 0: check.append((i, j))
        else:
            row[i][num] = True
            col[j][num] = True
            k = (i // 3) * 3 + j // 3
            square[k][num] = True


func(0) # check배열 첫 번째 좌표 값부터 백트래킹 시작