[2239] 스도쿠

문제

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

풀이

보드의 왼쪽 위부터 빈 곳에 입력 가능한 숫자를 넣어보는 방식으로 풀었습니다.

먼저 입력 가능한지 여부를 반환하는 함수를 만들어 줍니다.

첫 번째로 같은 행과 열에 같은 숫자가 존재하는지 확인 해줍니다. 간단하게 구할 수 있습니다.

두 번째는 3*3짜리 사각형에 같은 숫자가 존재하는지 확인해줘야합니다. 각 행과 열에 3을 나누고, 다시 3을 곱해주면 현재 위치가 속해있는 사각형의 가장 왼쪽 위의 좌표를 구할 수 있고, 해당 좌표에서부터 9칸을 탐색하면 같은 숫자가 존재하는지 여부를 알 수 있습니다.

import sys

board = []
empty = []

for r in range(9):
    row = list(map(int, sys.stdin.readline().strip()))
    board.append([])
    for c, n in enumerate(row):
        board[r].append(n)
        if n == 0:
            empty.insert(0, (r, c))

def is_possible(r, c, num):
    if num in board[r]: # 같은 행에 존재하는지 확인
        return False
    for i in range(9): # 열
        if num == board[i][c]:
            return False
    s_r, s_c = 3 * (r // 3), 3 * (c // 3)
    for i in range(s_r, s_r + 3):
        for j in range(s_c, s_c + 3):
            if board[i][j] == num:
                return False
    return True

def dfs():
    if not empty:
        for row in board:
            print(''.join(map(str, row)))
        exit()
    cur_r, cur_c = empty[-1]
    for num in range(1, 10):
        if is_possible(cur_r, cur_c, num):
            board[cur_r][cur_c] = num
            empty.pop()
            dfs()
            empty.append((cur_r, cur_c))
            board[cur_r][cur_c] = 0

dfs()