[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 2239번 _ 스도쿠

https://www.acmicpc.net/problem/2239

2239번: 스도쿠

[문제]

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

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

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

 

[입력]

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

[출력]

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

 

[아이디어]

1) 1~9를 순차적으로 채우길 시도하면서, 실패하면 백트래킹으로 돌아와야한다.

2) 스도쿠가 완성되면 출력하고, 이후 남은 케이스를 찾기 위한 재귀를 그만하도록 return 해버린다. (cnt = 1)

 

g = [list(map(int,list(input()))) for _ in range(9)]
visit = [[[0]*9 for _ in range(9)] for _ in range(3)]

for i in range(9):
    for j in range(9):
        if g[i][j]!=0:
            x = g[i][j] - 1
            visit[0][i][x] = visit[1][j][x] = visit[2][(i//3)*3+j//3][x] = 1
            
import sys
sys.setrecursionlimit(10**5)
cnt = 0
def sudoku(i,j):
    global cnt
    if i == 9:
        cnt +=1
        for i in range(9):
            print(''.join(map(str,g[i])))
        return
    if cnt ==1:
        return
    if g[i][j] > 0:
        if j==8:
            sudoku(i+1,0)
        else:
            sudoku(i,j+1)
    else:
        for k in range(9):
            if visit[0][i][k] == visit[1][j][k] == visit[2][(i//3)*3+j//3][k] == 0:
                g[i][j] = k+1
                visit[0][i][k] = visit[1][j][k] = visit[2][(i//3)*3+j//3][k] = 1
                if j==8:
                    sudoku(i+1,0)
                else:
                    sudoku(i,j+1)
                visit[0][i][k] = visit[1][j][k] = visit[2][(i//3)*3+j//3][k] = 0
                g[i][j] = 0
sudoku(0,0)

pypy3로 제출해야 통과할 수 있고, Python3로는 무조건 시간초과가 나는 것 같다. 백트래킹임을 처음에 떠올리지 못했고, 그 이후로도 한참을 헤맸다,, 다음으로 진입하고 되돌려놓는 간단한 원리인데 g[i][j]를 0으로 돌려놓는 걸 자꾸 빼먹은 채로 생각했다.