2580 - 스도쿠 [백트래킹]]

출처 : 백준 2580 스도쿠

문제

스도쿠가 주어지고 중간 중간에 0들이 있다. 해당 숫자들을 스도쿠 규칙에 맞게 알맞는 숫자로 대체해야 한다. 총 3가지의 조건을 확인해야 한다: 대체하려고 하는 숫자가 가로에 존재하는지, 세로에 존재하는지, 혹은 3x3칸에 존재하는지. 이 조건들을 확인하는 이유는 가로, 세로, 3x3에 1~9 숫자들 딱 한번씩만 나와야하기 때문이다.

문제가 풀리기는 했지만, Pypy3에서만 성공적으로 제출되었고 Python3에서는 시간초과가 발생했다. 알고리즘적으로 3개의 조건을 확인하는 것이 오래 걸렸던 것 같다. 다른 사람들의 풀이를 보니, 조건들을 3번에 나눠서 확인하는 것이 아닌 한번에 푼 사람들이 있었다. Python3에서는 그러한 방법으로 풀어야지만 시간초과가 발생하지 않을 것 같다.

풀이

import sys
r = sys.stdin.readline

# 가로 체크
def horizontal(x, val):
    if val in sudoku[x]:
        return False
    return True

# 세로 체크
def vertical(y, val):
    for i in range(9):
        if val == sudoku[i][y]:
            return False
    return True

# 3x3 체크
def bythree(x, y, val):
    nx = x//3 * 3
    ny = y//3 * 3
    for i in range(3):
        for j in range(3):
            if val == sudoku[nx+i][ny+j]:
                return False
    return True


def DFS(index):
    if index == len(zeros):
        for row in sudoku:
            for n in row:
                print(n, end=" ")
            print()
        sys.exit(0)
    else:
        for i in range(1, 10):
            nx = zeros[index][0]
            ny = zeros[index][1]

            # 세로, 가로, 3x3에 내가 대체하려고하는 숫자가 존재하는지 확인
            if horizontal(nx, i) and vertical(ny, i) and bythree(nx, ny, i):
                sudoku[nx][ny] = i
                DFS(index+1)
                sudoku[nx][ny] = 0


sudoku = [list(map(int, r().split())) for _ in range(9)]
zeros = [(i, j) for i in range(9) for j in range(9) if sudoku[i][j] == 0]
DFS(0)