[백준] 2580 스도쿠 (Python)

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

이 문제는 말 그대로 스도쿠가 주어졌을 때 빈칸을 채우는 문제이다.

끝내지 못한 코드

처음에는 이 문제에 DFS를 어떻게 녹여내야할지 감이 오지 않았다.
그래서 일단 가로, 세로, 박스를 체크하는 코드를 작성했다.

코드가 너무 길어서 중간에 find_verti 함수와 find_box 함수는 생략했다.

만약 각 find 함수에서 빈칸이 하나여서 빈 숫자를 바로 유추할 수 있다면 바로 값을 삽입하도록 했고, 그렇지 않다면 set에 빈칸에 대한 후보 숫자들을 담았다.

반환된 후보 숫자의 세트를 이용하게 되면 코드가 훨씬 더 복잡해지고 DFS를 사용하는 것이 의미가 없어지겠다고 생각해서 코드 작성을 멈추고 또 다시 블로그 서칭에 들어갔다.

import sys

input = sys.stdin.readline

def find_hori(x, y):
    candi = []

    num = []
    cnt = 0
    for i in range(9):
        if i == y:
            continue
        if sudoku[x][i] != 0:
            num.append(sudoku[x][i])
            cnt += 1

    if cnt == 8:
        for i in range(1, 10):
            if i not in num:
                return [i]

    for i in range(1, 10):
        if i not in num:
            candi.append(i)

    return candi


#
# 중간 코드 생략 ....
#


def find(x, y):
    print(x, y)
    # 후보 찾기
    candidate = set()

    # 가로 확인
    hori = find_hori(x, y)
    print("h", hori)
    if len(hori) == 1:
        return hori[0]

    # 세로 확인
    verti = find_verti(x, y)
    print("v", verti)
    if len(verti) == 1:
        return verti[0]

    # 9칸 확인
    box = find_box(x, y)
    print("b", box)
    if len(box) == 1:
        return box[0]

    candidate = set(hori).union(set(verti), set(box))

    return candidate


sudoku = [list(map(int, input().split())) for _ in range(9)]

for i in range(9):
    for j in range(9):
        if sudoku[i][j] == 0:
            candidate = find(i, j)
            if len(candidate) == 1:
                sudoku[i][j] = candidate.pop()
                

맞은 코드

스도쿠 빈칸의 인덱스를 blank 배열에 저장해주었다.
blank에 있는 인덱스를 다 거쳐 빈칸을 다 메꿔주면 결과값을 출력하고 dfs에서 exit을 한다.

check_x 함수를 통해 가로, 세로, 박스의 9칸 중 숫자 n이 없다면 True를 반환하여 빈칸에 n을 채우고,
dfs(idx+1)로 다음 인덱스에 대한 서칭을 진행하며 빈칸에 맞는 숫자를 찾는다.

import sys

input = sys.stdin.readline

sudoku = [list(map(int, input().split())) for _ in range(9)]


def check_hor(x, num):
    for i in range(9):
        if num == sudoku[x][i]:
            return False
    return True


def check_ver(y, num):
    for i in range(9):
        if num == sudoku[i][y]:
            return False
    return True


def check_box(x, y, num):
    a = x // 3 * 3
    b = y // 3 * 3
    for i in range(a, a + 3):
        for j in range(b, b + 3):
            if num == sudoku[i][j]:
                return False
    return True


def dfs(idx):
    # 빈칸을 다 메꿨으면 결과값 출력
    if idx == len(blank):
        for i in range(9):
            print(*sudoku[i])
        exit(0)

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

        if check_hor(x, n) and check_ver(y, n) and check_box(x, y, n):
            sudoku[x][y] = n
            dfs(idx + 1)
            sudoku[x][y] = 0


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

idx = 0
dfs(idx)

회고

check_box 함수에서 특정 빈칸이 9개의 스도쿠 박스 중 어느 박스에 속하는지 a = x // 3 * 3와 b = y // 3 * 3를 사용한 부분에서 내가 정말 코테를 요새 안풀었구나 하는 생각이 들었다. 나는 두줄로 끝나는 코드를 3x3 if문으로 적었으니..! 반성하기.

그리고 가로, 세로, 박스 확인하는 부분도 내 코드에 비해 코드가 너무 깔끔하다. 이것 또한 많이 풀다보면 늘겠지

dfs의 if문에서 exit()자리에 return이 있어도 되지 않나라는 생각을 했는데, 그렇게 되면 dfs로 깊게 들어왔기 때문에 들어온 길로 다시 나가야하므로 말이 안된다.

마지막으로 나는 백트랙킹에 너무너무 취약한 것 같다. 내일도 백트랙킹을 문제를 하나 더 풀어봐야겠다.