파이썬(python) 백준 2580 : 스도쿠
백준 2580 : 스도쿠
문제 내용
시간 제한 : 1 초
메모리 : 256 MB
baekjoon의 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 다음은 그 알고리즘의 수행 시간이다.
- C++14: 80ms
- Java: 292ms
- PyPy3: 1172ms
문제
아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다.
스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
입력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
출력
첫째 줄에 정답을 출력한다.
예제 입력 1
0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0
예제 출력 1
1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1
유형
알고리즘 분류
풀이
이 문제는 백트래킹 알고리즘 문제이다.
dfs 재귀함수를 하나 작성하여 풀면 된다.
1. 0이 등장하는 위치 차례로 방문
2. 대각선 + 가로줄 + 세로줄 검사하여 1~9까지 숫자 중 겹치지 않는 숫자 넣기
- 대각선 검사는 [0,1,-1] 리스트를 중복순열 사용하여 9개의 offset을 만들어서 했다.
3. 백트랙킹 : 그러한 숫자가 없으면 이전 상태로 되돌아가기
import sys
import itertools
board = [list(map(int, sys.stdin.readline().split())) for _ in range(9)]
zero_pos = [(x,y) for x in range(9) for y in range(9) if board[x][y] == 0]
z_len = len(zero_pos)
offset = list(itertools.product([1,-1,0],repeat=2))
offset_pos = [1]*3+[4]*3+[7]*3
finished = False
def choice(x,y):
nums = list(range(1,10))
for n in range(9):
if board[x][n] in nums:
nums.remove(board[x][n])
if board[n][y] in nums:
nums.remove(board[n][y])
for off in offset:
dx = offset_pos[x]+off[0]
dy = offset_pos[y]+off[1]
if board[dx][dy] in nums:
nums.remove(board[dx][dy])
return nums
def dfs(cur):
global finished
if finished == True :
return
if cur == z_len:
for item in board:
print(*item)
finished = True
return
else:
(x,y) = zero_pos[cur]
for c in choice(x,y):
board[x][y] = c
dfs(cur+1)
board[x][y] = 0
dfs(0)