[백준] 2239번 - 스도쿠 (파이썬)

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

# 스도쿠
import sys
input = sys.stdin.readline
N = 9
arr = []
empty = []
for i in range(N):
    arr.append(list(input().strip()))
    for j in range(N):
        if arr[i][j] == '0':
            empty.append((i, j))


def add_num(k):
    global isDone
    if k == len(empty):
        isDone = True
        return
    temp = check_available_num(empty[k][0], empty[k][1])
    for x in temp:
        arr[empty[k][0]][empty[k][1]] = x
        add_num(k+1)
        if isDone:
            return
        arr[empty[k][0]][empty[k][1]] = '0'


def check_available_num(x, y):
    temp = []
    for target in range(1, N+1):
        target = str(target)
        if check_rcs(x, y, target):
            temp.append(target)
    return temp


def check_rcs(x, y, target):
    for j in range(N):
        if arr[x][j] == target:
            return False
    for i in range(N):
        if arr[i][y] == target:
            return False
    temp_x = x // 3 * 3
    temp_y = y // 3 * 3
    for i in range(temp_x, temp_x+3):
        for j in range(temp_y, temp_y+3):
            if arr[i][j] == target:
                return False
    return True


isDone = False
add_num(0)
for i in range(N):
    print(''.join(arr[i]))

 

백트랙킹

1. 입력 받을 때 '0'인 좌표를 empty리스트에 따로 append한다.

2. check_available_num : 1~9까지의 수 중에서 check_rcs를 통과한 숫자들의 리스트를 반환

    - 1부터 숫자를 append해야 문제의 조건인 '답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력'을 만족

3. check_rcs : row, column, square를 확인해서 해당 숫자가 스도쿠의 조건에 맞는지 확인

4. 백트랙킹을 이용해서 empty를 하나씩 채워나간다.

5. 결과값을 join을 이용해서 출력

 

예전에 풀었던 2252번 스도쿠문제와 똑같은 원리의 문제라서 쉽게 풀었다.

 

[백준] 2252번 - 스도쿠

[백준] 2252번 - 스도쿠 (파이썬)