https://www.acmicpc.net/problem/2239
2239번: 스도쿠
스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다
www.acmicpc.net
풀이 1, 풀이 2 모두 PyPy3 기준 AC 가능(통과 가능)
풀이 1
Backtracking을 이용해 풀 수 있는 문제.
스도쿠를 이차원 배열에 저장하고, 0이 있는 좌표들을 리스트에 저장.
백트래킹을 이용해 모든 0이 있는 칸에 가능한 숫자를 채워준다.
recursion의 depth는 9x9 스도쿠이기 때문에 최대 81. recursion error를 걱정할 만한 깊이가 아니니 안심하고 진행.
처음엔 풀이 1대로 풀었다가 TLE가 나와 더 시간을 줄여야 하나? 싶어서, 풀이 2와 같이 rowCheck, colCheck 또한 boxCheck처럼 이차원 배열에 저장하는 방식으로 변경해 풀었다.
그런데 다시 보니 TLE가 나는 이유가 프로그램이 끝나지 않아서였고.. ^ㅁ^ exit() 을 넣어줌으로써 해결했다.
물론 풀이 2가 더 시간이 적게 걸리긴 하지만, 풀이 1, 풀이 2 모두 AC!
board = [list(map(int, input())) for _ in range(9)]
coors = []
'''0이 들어간 좌표 저장'''
for i in range(9):
for j in range(9):
if board[i][j] == 0:
coors.append((i, j))
def rowCheck(n, row):
if n in board[row]:
return True
return False
def colCheck(n, col):
for i in range(9):
if n == board[i][col]:
return True
return False
'''boxCheck[n][m-1] = n번 box에 m이 포함되었는지'''
boxCheck = [[False] * 9 for _ in range(9)]
for i in range(9):
for j in range(9):
if board[i][j] != 0:
boxCheck[(i//3)*3 + j//3][board[i][j]-1] = True
def backT(n):
'''coors(0의 좌표들) 의 개수만큼 depth가 깊어졌다면, 모든 0에 숫자를 채워넣은 상태이므로, 종료.'''
if n == len(coors):
for b in board:
print(*b, sep="")
exit()
'''i, j = row, column'''
i, j = coors[n]
for k in range(1, 10):
if rowCheck(k, i):
continue
if colCheck(k, j):
continue
if boxCheck[(i//3)*3 + j//3][k-1]:
continue
'''row, col, box check 후 숫자 삽입'''
board[i][j] = k
boxCheck[(i//3)*3 + j//3][k-1] = True
backT(n+1)
'''만약 더 깊은 depth에서 return이 일어났다면, backTracking을 위해 원상복구.'''
board[i][j] = 0
boxCheck[(i//3)*3 + j//3][k-1] = False
backT(0)
풀이 2
board = [list(map(int, input())) for _ in range(9)]
coors = []
'''0이 들어간 좌표 저장'''
for i in range(9):
for j in range(9):
if board[i][j] == 0:
coors.append((i, j))
'''rowCheck[n][m-1] = n번 row에 m이 포함되었는지'''
rowCheck = [[False] * 9 for _ in range(9)]
'''colCheck[n][m-1] = n번 column에 m이 포함되었는지'''
colCheck = [[False] * 9 for _ in range(9)]
'''boxCheck[n][m-1] = n번 box에 m이 포함되었는지'''
boxCheck = [[False] * 9 for _ in range(9)]
for i in range(9):
for j in range(9):
if board[i][j] != 0:
boxCheck[(i//3)*3 + j//3][board[i][j]-1] = True
rowCheck[i][board[i][j]-1] = True
colCheck[j][board[i][j]-1] = True
def backT(n):
'''coors(0의 좌표들) 의 개수만큼 depth가 깊어졌다면, 모든 0에 숫자를 채워넣은 상태이므로, 종료.'''
if n == len(coors):
for b in board:
print(*b, sep="")
exit()
'''i, j = row, column'''
i, j = coors[n]
for k in range(1, 10):
if rowCheck[i][k-1]:
continue
if colCheck[j][k-1]:
continue
if boxCheck[(i//3)*3 + j//3][k-1]:
continue
'''row, col, box check 후 숫자 삽입'''
board[i][j] = k
boxCheck[(i//3)*3 + j//3][k-1] = True
rowCheck[i][k-1] = True
colCheck[j][k-1] = True
backT(n+1)
'''만약 더 깊은 depth에서 return이 일어났다면, backTracking을 위해 원상복구.'''
board[i][j] = 0
boxCheck[(i//3)*3 + j//3][k-1] = False
rowCheck[i][k-1] = False
colCheck[j][k-1] = False
backT(0)