백준 2580 - 스도쿠 python

처음 든 생각

- 행, 열, 3*3 모두 고려를 해줘야겠네

- 무조건 1개만 남겨저서 풀 수 있는 놈이 있을테니 그걸 중심으로 풀어나가면 되겠다

-> 라고 생각한 것이 크나큰 오산이었다.

 

예를 들어 어떤 0은 열을 검사했을 때는 1,2가 가능하고 행을 검사했을 때 2,3,6이 가능하다고 했으면 이 녀석은 2로 확정지을 수 있다.

즉, 무조건 1개만 남겨져서 풀겠다는 어마어마한 경기도 오산이었고 오직 예제에서만 가능한 경우였다. 가능한 후보군에 대하여 하나하나씩 다 검사를 했어야 한다.

 

(답지 보고 푼) 나의 답

import sys
input = sys.stdin.readline

s = []
zero_q = []
for i in range(9):
    temp_list = list(map(int, input().split()))
    s.append(temp_list)
    for j in range(9):
        if temp_list[j] == 0:
            zero_q.append([i,j])

# 해당 행에 a가 있는지 없는지 확인
def checkRow(r,a):
    for i in range(9):
        if s[r][i] == a:
            return False
    return True

# 해당 열에 a가 있는지 없는지 확인
def checkCol(c,a):
    for i in range(9):
        if s[i][c] == a:
            return False
    return True

# 해당 3*3에 a가 있는지 없는지 확인
def checkSquare(r,c,a):
    nr = r//3 *3
    nc = c//3 *3
    for i in range(3):
        for j in range(3):
            if a == s[nr+i][nc+j]:
                return False
    return True

# 모든 0 좌표들에 대하여 dfs 수행
def dfs(idx):
    if idx == len(zero_q):
        for i in range(9):
            print(" ".join(map(str,s[i])))
        exit()
    for i in range(1,10):
        r = zero_q[idx][0]
        c = zero_q[idx][1]
        # 0인 좌표에 1~9까지 넣어보면서 가능한지 확인
        if checkRow(r,i) and checkCol(c,i) and checkSquare(r,c,i):
            s[r][c] = i
            dfs(idx+1)
            # 만약에 넣어봤다가 더이상 dfs 함수 스택이 쌓이지 않거나 exit가 안 된거면 다시 0으로 바꿔서 다음 수를 대입
            s[r][c] = 0
dfs(0)

 

행, 열, 작은 정사각형에 대하여 a가 있는지 없는지 확인하고 만약 a 값이 있다면 얘는 들어갈 수 없는 놈이기에 False를 리턴해준다.

 

그다음 노드 하나씩 DFS를 수행해나간다. 즉, 될 때까지 깊게 파는 거다.

0인 좌표들에 대해서 1~9까지 가능한 숫자를 찾은 후에 가능하다면 대입하고 그 다음 노드에 대하여 DFS를 수행한다. 만약 다음 DFS를 실행했을 때 1~9까지 가능한 숫자가 없다면 함수 스택이 쌓이지 않기에 다음 수를 대입해야 한다. 그렇게 0으로 초기화를 시켜준 후 새로운 i값을 대입하는 백트래킹 알고리즘이었다.

---

처음 구현한 알고리즘은 이거였다.

import sys
from collections import deque
input = sys.stdin.readline

s = []
row_zero = [0 for _ in range(9)]
col_zero = [0 for _ in range(9)]
square_zero = [ [0 for _ in range(3)] for _ in range(3)]
zero_q = deque([])


for i in range(9):
    temp_list = list(map(int, input().split()))
    s.append(temp_list)
    for j in range(9):
        if temp_list[j] == 0:
            row_zero[i] += 1
            col_zero[j] += 1
            square_zero[i//3][j//3] += 1
            zero_q.append([i,j])

while zero_q:
    temp = zero_q.popleft()
    if row_zero[temp[0]] == 1:
        s[temp[0]][temp[1]] = 45 - sum(s[temp[0]])
        row_zero[temp[0]] -= 1
        col_zero[temp[1]] -= 1
        square_zero[temp[0]//3][temp[1]//3] -= 1
        continue
    elif col_zero[temp[1]] == 1:
        sum_col = 0
        for k in range(9):
            sum_col += s[k][temp[1]]
        s[temp[0]][temp[1]] = 45 - sum_col
        row_zero[temp[0]] -= 1
        col_zero[temp[1]] -= 1
        square_zero[temp[0]//3][temp[1]//3] -= 1
        continue
    elif square_zero[temp[0]//3][temp[1]//3] == 1:
        sum_square = 0
        for m in range(temp[0]//3 * 3,temp[0]//3 * 3 + 3):
            for n in range(temp[1]//3 * 3 , temp[1]//3 * 3 + 3):
                sum_square+= s[m][n]
        s[temp[0]][temp[1]] = 45 - sum_square
        row_zero[temp[0]] -= 1
        col_zero[temp[1]] -= 1
        square_zero[temp[0]//3][temp[1]//3] -= 1
        continue
    zero_q.append(temp)
        
for r in s:
    print(" ".join(map(str, r)))

 

큐로 0의 좌표들을 관리한 다음 0의 개수가 1개인 놈이라면 확정을 지을 수 있기 때문에 찾아서 넘어가고 아니면 다시 뒤로 append해서 나중에 다른 좌표들 조사가 끝났을 때 다시 계산하는 방식으로 했다.

 

예제도 올바르게 나왔으나 애초에 스도쿠의 아이디어 자체가 잘못된 것이었다.

 

괜히 틀린 알고리즘 구경하다가 눈 버릴 수도 있으니 자세히 살펴보지 말고 그냥 이렇게 풀어서 틀린 놈도 있구나~하고 넘어가면 된다.

 

---

일단 DFS를 접목시켜서 백트래킹을 할 생각을 못한 것은 경험치가 정말 부족하다는 것을 방증하는 것이었다. 

 

실제로 답안 코드를 처음 봤을 때도 한 번에 이해는 되지 않았다. 갑자기 DFS?? 이런 느낌이었다.

하지만 결국 한 놈을 죽도록 팬다는 DFS의 철학을 대입시켜보면 스도쿠와 정확히 통한다.

 

이 문제는 기필코 이번주에 다시 복습하면서 새로 풀어봐야겠다.

아마 다시 풀어보면 못 풀 확률이 높아보이지만...