[백준 #2580 파이썬] 스도쿠

으음 반은 풀고 반은 몰랐던 문제

보자마자 이건 백트래킹이다! 라고 생각할만한 요소가 많았다.

한 칸에 여러 경우의 수가 올 수 있었고 그 수가 완성이 되어야 최적의 값을 탐색할 수 있다는 점은 당연히 백트래킹을 연상할 수 밖에 없었다.

그런데 어떻게 푸냐가 항상 문제지 ㅎㅎ

 

생각

그래서 그냥 스도쿠를 푸는 방식을 먼저 생각해봤다.

1. 가로

2. 세로

3. 3 * 3 사각형 내

가장 기본적으로 생각해볼 수 있는 방법이었다.

 

이제 구현하는 과정에서 bfs를 줄기차게 풀던 시절을 떠올리며 문제를 풀어보았다.

우선 0인 값을 모두 찾아 저장해준다. 그리고 그 값들마다 저 세개의 검증 과정을 거치자

 

그런데 함수를 구현하는 방법에서 스도쿠 숫자 1~9까지 탐색하는 방법에 고민이 많았다.

첫째는 각 함수마다 없는 값들을 찾아 후보를 추리고 이를 조합하는 방법과,

둘째는 모든 함수에 1~9를 넣어 가능 여부를 판단하는 것이다.

 

첫번째 방법이 가장 먼저 떠올랐지만, 탐색 과정과 이후 처리 과정에서 조합을 처리함에 있어 시간복잡도가 그렇게 좋아보이지는 않아보여 패스 (그래도 나중에 도전해보는 것도 나쁘지 않을 듯 하다)

 

두번째 방법으로 구현을 해보았다

def square(x,y,a):
    nx,ny = x//3*3,y//3*3
    for i in range(3):
        for j in range(3):
            if a == sdoku[nx+i][ny+j]:
                return False
    return True
            
def row(x,a):
    for i in range(9):
        if a == sdoku[x][i]:
            return False
    return True

def col(y,a):
    for i in range(9):
        if a == sdoku[i][y]:
            return False
    return True

다른 것은 이해되겠지만, a는 1부터 9까지 모두 값을 넣어 판정하는 부분이다.

a 라는 값이 스도쿠 규칙에 따라 탐색하는 과정에서 발견되지 않아야 스도쿠를 채울 수 있는 숫자 후보가 된다.

그 숫자 후보가 되면, 백트래킹에 적용해볼 수 있는 하나의 값이 되는 것이다!

 

여기서 sqaure 함수의 조건처리는 답을 참고했다. nx,ny를 처리하는 게 어려웠다.

어느 사각형 소속인지 판정할 수 있도록 몫을 활용하였다. 

이렇게 몫을 활용해서 값을 처리해주는 방법이 많은 것 같으니 이제는 기억해두는 게 도움이 될 듯 하다.

 

이제는 이 함수들을 어떻게 구현해야 하나 고민이 많았다.

우선 백트래킹의 기본 문제, 평범한 배낭을 다시 생각해봤다

평범한 배낭은 값을 비교하여 무게라는 제한조건 내에서 최적의 가치를 가지는 물건을 선정하는 과정이었다.

여기서도 살펴보면 문제풀이는 스도쿠의 세가지 제한조건 내에서 최적의 결과를 탐색하는 과정이다.

 

배낭 문제도 무조건 값을 넣고 비교를 거쳐야만 어떤 것이 최적의 값인지 판단할 수 있었다.

그런데 차이가 있다면 평범한 배낭 문제는 무게를 비교해보고 사라지는 값들이 존재한다.

하지만 이 문제는 조건을 따져보며 판정을 하다 조건이 맞지 않으면 값을 되돌려 놔야 한다.

 

딱 여기까지만 고민해보고,,,어떻게 구현해야 할 지 고민해보다가 포기하고 답을 참고했다.

 

ㅋㅋㅋㅋ진짜 어이없지만 생각한 내용이 바로 dfs 그 자체였다!

그래도 idx를 활용해서 탈출 조건을 만들고 chk 부분을 처리하는 방법은 꽤나 신박한 방법이었다.

이 부분도 잘 기억해 둬야겠다 :)

 

sdoku = []
chk = []
for i in range(9):
    sdoku.append(list(map(int,input().split())))

for i in range(9):
    for j in range(9):
        if sdoku[i][j] == 0:
            chk.append([i,j])
            
def square(x,y,a):
    nx,ny = x//3*3,y//3*3
    for i in range(3):
        for j in range(3):
            if a == sdoku[nx+i][ny+j]:
                return False
    return True
            
def row(x,a):
    for i in range(9):
        if a == sdoku[x][i]:
            return False
    return True

def col(y,a):
    for i in range(9):
        if a == sdoku[i][y]:
            return False
    return True

def dfs(idx):
    if idx == len(chk):
        for i in range(9):
            print(*sdoku[i])
        exit(0)

    for i in range(1,10):
        x = chk[idx][0]
        y = chk[idx][1]

        if row(x,i) and col(y,i) and square(x,y,i):
            sdoku[x][y] = i
            dfs(idx + 1)
            sdoku[x][y] = 0

dfs(0)