[🥇4 / 백준 2580 / 파이썬] 스도쿠

 

2580번: 스도쿠

 

문제

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

 

제한

• baekjoon의 백트래킹 알고리즘으로 풀 수 있는 입력만 주어진다. 다음은 그 알고리즘의 수행 시간이다.
  • C++14: 80ms
  • Java: 292ms
  • PyPy3: 1172ms

예제 입력 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 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

 

풀이

 

스도쿠 자동 풀이 알고리즘을 작성하는 문제이다.

이번 문제는 시간 제한이 빡빡한 것 같아서 개인적으로 조금 힘들었던 것 같다.

 

맨 처음 시도한 방법은, 그저 가로, 세로, 3x3 박스를 비교하여

0에 들어갈 수 있는 숫자가 하나 뿐일 때 이것을 입력해주고 이를 무한 반복하여 풀어나가는 방식이다.

 

예제는 풀렸으나, 다른 경우에 숫자를 꼭 두개 중 하나 찍어야 하는 상황이 왔을 때

당연히 무한루프에 걸렸고 문제를 풀 수 없었다.

 

애초에 백트래킹 문제인데 처음부터 잘못 생각했다고 할 수 있다.

 

 

그 다음 시도한 방법은 우선 불필요한 반복을 줄이기 위해 0의 좌표를 추출하고 시작했다.

그리고 깊이 우선 탐색(DFS)을 통해 풀기로 했다.

 

해당 0에 들어갈 수 있는 숫자 리스트를 추출하고

이를 바탕으로 차례대로 찍어나가며 재귀를 통해 해결하는 방법이다.

 

import sys
sudoku = [list(map(int,sys.stdin.readline().split())) for i in range(9)]

loc = [[i,j] for i in range(9) for j in range(9) if sudoku[i][j] == 0]

def dfs(n):
    if n == len(loc):
        for i in sudoku:
            print(*i)
        sys.exit(0)
        # 문제가 풀렸으므로 종료
        return
    
    row,col = loc[n]
    nums = [i for i in range(1,10)]
    
    for i in sudoku[row]:  # 가로행 비교
        if i in nums:
            nums.remove(i)
        
    for i in range(9):     # 세로행 비교
        if sudoku[i][col] in nums:
            nums.remove(sudoku[i][col])
    
    a,b = row//3, col//3   # 박스 비교
    for i in range(a*3, (a+1)*3):
        for j in range(b*3, (b+1)*3):
            if sudoku[i][j] in nums:
                nums.remove(sudoku[i][j])
    
    for i in nums:
        sudoku[row][col] = i
        dfs(n+1)
    sudoku[row][col] = 0
    # 위 숫자들이 모두 정답이 아닐 수 있으니 초기화
    
dfs(0)

 

스도쿠가 정상적으로 풀렸고, 문제도 정답으로 인정되었다.

 

단, Pypy3로 제출해야한다.

 

 

시간을 더 줄일 수 있는 방법에 대해 고민해봤는데,

 

입력이 예를 들어

 

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 4

0 0 9 0 0 0 2 7 0

0 4 3 2 0 7 9 0 0

0 8 0 1 9 0 4 5 0

0 2 8 0 6 1 5 0 9

5 0 0 9 0 0 6 8 2

4 9 0 0 0 8 0 0 0

 

위와 같을 경우 검사 시작 부분에 0이 극단적으로 많이 포진해 있기 때문에

저 많은 경우의 수를 모두 돌려봐야 해서 쓸데없는 자원 낭비를 심하게 한다는 것이다.

 

따라서 무작정 0을 왼쪽 상단부터 순서대로 대입하는 검사하는 것이 아닌,

대입해 볼 숫자가 적은 순서대로 검사하는 알고리즘을 짠다면 시간을 많이 줄일 수 있을 것 같다.