[BaekJoon] 2239 스도쿠 (Gold 4) - Python

문제

 

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

---

입출력 예시

 

입력: 9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력: 9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

제한:

• 12095번 문제에 있는 소스로 풀 수 있는 입력만 주어진다.
  • C++17: 180ms
  • Java 15: 528ms
  • PyPy3: 2064ms

 

입력예시1)

103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

출력예시1)

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

---

코드

 

import sys; input = sys.stdin.readline

grid = [list(map(lambda x: int(x), list(input().rstrip()))) for _ in range(9)]
empty = []
for i in range(9):
    for j in range(9):
        if grid[i][j] == 0:
            empty.append((i, j))

def dfs(i):
    if i == len(empty):
        for a in grid:
            print(''.join(map(str, a)))
        return True
    
    x, y = empty[i][0], empty[i][1]
    total_number = set([num for num in range(1,10)])
    used = set(grid[x] + [grid[r][y] for r in range(9)] + [grid[r][c] for r in range(3*(x//3),3*(x//3)+3) for c in range(3*(y//3), 3*(y//3) +3)])
    for num in sorted(total_number - used):
        grid[x][y] = num
        if dfs(i + 1):
            return True
        grid[x][y] = 0
    return False
        
dfs(0)

---

실행 화면

 

---

채점 결과