[BOJ] 2239. 스도쿠 (python)

 

✏️ 문제

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

example

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.
하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

 

🤖 알고리즘

 

#구현  #백트래킹

 

 

🤯 풀이 방법

 

한 칸을 기준으로 가로, 세로, 사각형 안에 있는 값을 모두 기록해두는 배열을 하나 만들고 그 배열에 없는 수 중 가장 작은 값을 리턴하는 함수를 만든다. 이때 만약 예전에 한 번 탐색한 적이 있는 칸이라면 그 칸의 현재 값을 파라미터로 받아 그 다음부터 탐색하도록 한다.

전체 스도쿠판 중 값이 비어 있는 칸들의 인덱스를 모두 기록해두고 순서대로 탐색한다.

만약 답을 찾는 것이 불가능하다면 (함수의 리턴값이 -1이라면) 이전 인덱스의 값을 다시 탐색한다.

이때 되돌아가야 한다면 이후에 잘못 기록한 값을 0으로 지우고 이전 인덱스로 돌아가야 중복을 막을 수 있다.

 

👾 구현 코드 (파이썬)

import sys
input = sys.stdin.readline


def sudoku(ci, cj, k):  
	# ci: 행, cj: 열, k: 가능한 최소 값
    ex = [x for x in range(k)]
    for x in range(9):
        ex.append(board[ci][x])
        ex.append(board[x][cj])

    xx, yy = ci // 3 * 3, cj // 3 * 3
    for x in range(3):
        for y in range(3):
            ex.append(board[xx + x][yy + y])

    for x in range(k, 10):
        if x not in ex:
            return x
          
    return -1

board = []
blanks = []
for i in range(9):
    row = list(map(int, list(input().rstrip())))
    board.append(row)

# 채워야 하는 값들 인덱스 저장
for i in range(9):
    for j in range(9):
        if board[i][j] == 0:
            blanks.append([i, j])

i = 0

while 0 <= i < len(blanks):
    ni, nj = blanks[i][0], blanks[i][1]
    cur = board[ni][nj]
    res = sudoku(ni, nj, cur)
    if res == -1:
        board[ni][nj] = 0
        i -= 1
    else:
        board[ni][nj] = res
        i += 1

for i in range(9):
    ans = ''
    for ii in board[i]:
        ans += str(ii)
    print(ans)

 

2239번: 스도쿠