[알고리즘] 백준 2580 (파이썬)

처음 접근 방법: 앞의 0부터 탐색하여 가로 세로 묶음 보고 빈 숫자를 넣기
--> 모든 칸이 0으로 입력이 되는 것처럼 숫자 1개가 비는 것이 아니면 채워지지 않는다.

두 번째 방법: 백트래킹 방법
모든 0의 좌표를 넣고 리스트의 앞부터 백트래킹 시작

스도쿠가 완성되면 종료가 되어야 하므로 바로 return을 시켰음
--> 백트래킹이 되어야 하므로 pop을 넣어주지 않으면 아무 것도 나오지 않는다.

이 후 pop만 넣고 원래 좌표를 0으로 돌려주지 않았다. +스도쿠가 완성될 때 바로 끝내기 위해서 end변수를 사용하여 처음 스도쿠가 완성될 때 1을 증가시키고 재귀에서 나올 때 end변수를 통해 끝내도록 함
--> 이렇게 되면 숫자는 남아있으므로 계속 9가 남아있게 된다. (마지막 경우가 9이므로) 따라서 백트래킹 시에 영향을 미쳐서 결과가 나오지 않음

원래 좌표를 0으로 만들어줌
--> TLE가 떠서 백트래킹 조건 중 가로 세로 묶음을 모두 보고 다음 제로 숫자를 탐색할지 정하는 것을 각 조건마다 확인해서 틀리면 바로 넘기도록 함

1달만에 드디어 백트래킹 문제를 정복했다!!! 😃😃😃

코드

import sys

dp = []

for i in range(9):
    dp.append(list(map(int,sys.stdin.readline().split())))

num = [1,2,3,4,5,6,7,8,9]

zero = []
for i in range(9):
    for j in range(9):
        if dp[i][j] == 0:
            zero.append([i,j])


ans = []

def row(tar, co):
    x = co[0]
    y = co[1]

    target = dp[x]

    if tar in target:
        return 1
    else:
        return 0

def column(tar ,co):
    x = co[0]
    y = co[1]
    ans = 0
    for i in range(9):
        if dp[i][y] == tar:
            ans+=1
    return ans

def cluster(tar, co):
    x = (co[0] // 3) * 3
    y = (co[1] // 3) * 3
    ans = 0
    for i in range(3):
        for j in range(3):
            if dp[x+i][y+j] == tar:
                ans += 1

    return ans
end = 0
def zeros(n):
    global end
    # print(dp)
    if len(ans) == len(zero):
        end+=1
        for mmm in dp:
            print(*mmm)

        return

    for i in num:
        next = zero[n]

        n1 = row(i,next)
        if n1 != 0:
            continue

        n2 = column(i,next)
        if n2 != 0:
            continue
        n3 = cluster(i,next)
        if n3 != 0:
            continue
        # print(i, next, n1, n2, n3)


        ans.append(next)
        dp[next[0]][next[1]] = i
        zeros(n+1)

        if end > 0:
            return

        dp[next[0]][next[1]] = 0
        ans.pop()

zeros(0)