코딩테스트/python
백준_2239_스도쿠
zyin
2022. 3. 7. 18:51
문제
https://www.acmicpc.net/problem/2239
2239번: 스도쿠
스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다
www.acmicpc.net
풀이
1) dfs
깊이/너비 우선 탐색을 할 때 재귀를 잘 사용하지 않았다. 이 문제를 반복문으로 풀었더니, pypy3로 제출하더라도 시간초과가 발생했다. (물론 이 방법으로 푸는 다른 방법도 있겠지만... )
백트래킹이 필요한 경우에 기존에는 stack에 배열 자체를 넣어서 반복문을 돌렸는데,
이런 경우 재귀를 사용할 수 있음을 알아두자.
2) 논리
unknown에 0으로 표시된 위치 정보를 저장한다.
unknown에 들어갈 수 있는 candidate를 구한다.
- [1, 2, 3, 4, 5, 6, 7, 8, 9]에서
- 가로방향에 있는 숫자를 제거한다.
- 세로방향에 있는 숫자를 제거한다.
- 3*3 블록에 있는 숫자를 제거한다.
unknown에 들어갈 수 있는 값을 넣어보면서, 스도쿠가 완성되면 탐색을 멈춘다.
3) 제출
python으로 제출해서 시간초과를 통과하지 못했다. (pypy3로 제출했다)
코드
import sys
input = sys.stdin.readline
N = 9
board = [list(map(int, input().strip().split())) for i in range(N)]
rowCandidate = [set(range(1, N+1)) for i in range(N)]
colCandidate = [set(range(1, N+1)) for i in range(N)]
blockCandidate = [[set(range(1, N+1)) for j in range(N)] for i in range(N)]
flag = False # answer 한번만 출력
unknown = list()
for i in range(N) :
for j in range(N) :
# 각 행/열/블록마다 이미 들어있는 수를 제거
rowCandidate[i] -= {board[i][j]}
colCandidate[j] -= {board[i][j]}
blockCandidate[i//3][j//3] -= {board[i][j]}
# 비어있는 칸을 저장
if board[i][j] == 0 :
unknown.append((i, j))
def pprint() :
for i in range(N) :
for j in range(N) :
print(board[i][j], end = " ")
print()
def find(idx) :
global flag
if flag : return
if idx >= len(unknown) :
flag = True
pprint()
return
r, c = unknown[idx]
numberSet = rowCandidate[r] & colCandidate[c] & blockCandidate[r//3][c//3]
for num in numberSet :
board[r][c] = num
rowCandidate[r].remove(num)
colCandidate[c].remove(num)
blockCandidate[r//3][c//3].remove(num)
find(idx+1)
board[r][c] = 0
rowCandidate[r].add(num)
colCandidate[c].add(num)
blockCandidate[r//3][c//3].add(num)
find(0)