[백준]2239 스도쿠

1. 풀이

일반적엔 백트래킹문제. 아래 두가지만 주의하면 된다.

(1) 영역확인 잡기술

dR=[-1,-1,-1,0,0,0,1,1,1]
dC=[-1,0,1,-1,0,1,-1,0,1]

#영역 확인
    cR=(r//3)*3+1
    cC=(c//3)*3+1
    for i in range(9):
        tempR=cR+dR[i]
        tempC=cC+dC[i]
        if L[tempR][tempC]==num:
            return False

(2) 해당 depth 모두 탐색후 해당위치 다시 0으로 만들어놓기 주의

        for i in range(1,10):
            if isPossible(r,c,i):
                L[r][c]=i
                dfs(cnt+1)
        L[r][c]=0

*그런데 한가지 이상한점은 python3은 시간초과나서 pypy3으로 제출했는데, ​sys.setrecursionlimit(10**6)를 넣으면 터진다. 안붙여야 통과됨..

 

2. 소스코드

import sys
# sys.setrecursionlimit(10**6) 넣으면 터진다.
L=[]
for i in range(9):
    L.append(list(map(int,list(input()))))
dR=[-1,-1,-1,0,0,0,1,1,1]
dC=[-1,0,1,-1,0,1,-1,0,1]

# r,c에 num을 넣을 수 있는가?
def isPossible(r,c,num):
    #가로 확인
    if num in L[r]:
        return False
    #세로 확인
    if num in [L[i][c] for i in range(9)]:
        return False
    #영역 확인
    cR=(r//3)*3+1
    cC=(c//3)*3+1
    for i in range(9):
        tempR=cR+dR[i]
        tempC=cC+dC[i]
        if L[tempR][tempC]==num:
            return False

    return True

# cnt
def dfs(cnt):
    if cnt==81:
        for i in L:
            print("".join(map(str,i)))
        sys.exit()
    r=cnt//9
    c=cnt%9
    #해당위치에 숫자가 있으면 다음
    if L[r][c]!=0:
        dfs(cnt+1)
    else:
        #해당위치에 숫자가 없으면 넣는게 가능한숫자 넣고 다음진행
        for i in range(1,10):
            if isPossible(r,c,i):
                L[r][c]=i
                dfs(cnt+1)
        L[r][c]=0

dfs(0)