파이썬(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)