✏️ 문제
스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.
위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 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)
728x90
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ] 5430. AC (python) (1) | 2023.12.18 |
---|---|
[BOJ] 9465. 스티커 (python) (1) | 2023.08.27 |
[BOJ] 17281. ⚾ (python) (0) | 2023.08.05 |
[BOJ] 1138. 한 줄로 서기 (python) (2) | 2023.07.13 |
[BOJ] 21608. 상어 초등학교 (python) (1) | 2023.05.21 |