BAEKJOON PYTHON 2580 스도쿠

Prob

---

Approach

PyPy를 사용하여 제출한다.

미입력된 부분만 뽑아서 후보 숫자를 구해 백트래킹한다.

---

Code

import sys
m_board = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(9)]
prob = [(i, j) for i in range(9) for j in range(9) if m_board[i][j] == 0]

def candi_num(i, j):
    num = [k for k in range(1, 10)]
    
    for m in range(9):
        if m_board[i][m] in num:
            num.remove(m_board[i][m])
        if m_board[m][j] in num:
            num.remove(m_board[m][j])
    i = i // 3
    j = j // 3

    for p in range(i * 3, (i + 1) * 3):
        for q in range(j * 3, (j + 1) * 3):
            if m_board[p][q] in num:
                num.remove(m_board[p][q])
    return num

flag = False
def dfs(x):
    global flag
    
    if flag:
        return

    if x == len(prob):
        for k in range(len(m_board)):
            sys.stdout.write(' '.join(map(str, m_board[k])) + '\n')
        flag = True
        return
    else:
        (i, j) = prob[x]
        can_num = candi_num(i, j)
        for num in can_num:
            m_board[i][j] = num
            dfs(x + 1)
            m_board[i][j] = 0
dfs(0)

 

출처

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