[BOJ][Python][골4][2580] 스도쿠

문제 링크

문제링크

시간초과 나는 분들 pypy3로 제출해야합니다! python3로 이 문제 맞은 사람 13명밖에 없습니다!

첫 번째 풀이

정답코드

0의 좌표를 기준으로 백트레킹을 합니다.

import sys
from math import pi, sqrt
from collections import deque, Counter
from operator import itemgetter

# sys.stdin = open('input.txt', 'r')
arr = []
zeros = []
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:
            zeros.append((i, j))
n = len(zeros)
flag = False


def check(x, y):
    able = [i for i in range(1, 10)]
    for i in range(9):
        if arr[i][y] in able:
            able.remove(arr[i][y])
        if arr[x][i] in able:
            able.remove(arr[x][i])
    for i in range(3):
        for j in range(3):
            curr = arr[x // 3 * 3 + i][y // 3 * 3 + j]
            if curr in able:
                able.remove(curr)
    return able


def recur(depth):
    global n, flag
    if flag:
        return
    if depth == n:
        flag = True
        for i in range(9):
            print(*arr[i])
        return

    x = zeros[depth][0]
    y = zeros[depth][1]
    for k in check(x, y):
        arr[x][y] = k
        recur(depth + 1)
    arr[x][y] = 0


recur(0)

두 번째 풀이

정답코드

2차원 n자리 k진수를 기준으로 백트레킹을 합니다.

import sys
from math import pi, sqrt
from collections import deque, Counter
from operator import itemgetter

# sys.stdin = open('input.txt', 'r')
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]

flag = False


def check(x, y):
    able = [i for i in range(1, 10)]
    for i in range(9):
        if arr[i][y] in able:
            able.remove(arr[i][y])
        if arr[x][i] in able:
            able.remove(arr[x][i])
    for i in range(3):
        for j in range(3):
            curr = arr[x // 3 * 3 + i][y // 3 * 3 + j]
            if curr in able:
                able.remove(curr)
    return able


def recur(x, y):
    global flag
    if flag:
        return
    if y == 9:
        x += 1
        y = 0
    if x == 9:
        flag = True
        for i in range(9):
            print(*arr[i])
        return
    if arr[x][y]:
        recur(x, y + 1)
    else:
        for k in check(x, y):
            arr[x][y] = k
            recur(x, y + 1)
        arr[x][y] = 0


recur(0, 0)

Success Notice: 수고하셨습니다.