백준 #2580 스도쿠

원래 코드

import sys
# sys.stdin = open("input.txt")

def check(r, c, num):
    for i in range(9):  # 가로 방향 체크
        if i != c and arr[r][i]:
            if arr[r][i] == num:
                return False
    for i in range(9):  # 세로 방향 체크
        if i != r and arr[i][c]:
            if arr[i][c] == num:
                return False
    # 박스 체크
    r_ = r % 3
    c_ = c % 3
    for i in range(-r_, 3 - r_):
        for j in range(-c_, 3 - c_):
            if [i, j] != [0, 0] and arr[r + i][c + j]:
                if arr[r + i][c + j] == num:
                    return False
    return True

def solve(cur):
    if cur == m:
        for row in arr:
            print(*row)
        exit()

    cur_r, cur_c = blank[cur][0], blank[cur][1]
    for j in range(1, 10):
        if check(cur_r, cur_c, j):
            arr[cur_r][cur_c] = j
            solve(cur + 1)
            arr[cur_r][cur_c] = 0

arr = [list(map(int, input().split())) for _ in range(9)]
blank = []
for i in range(9):
    for j in range(9):
        if arr[i][j] == 0:
            blank.append((i, j))

m = len(blank)
solve(0)

수정 코드

### boj 2580 스도쿠

import sys
# sys.stdin = open("input.txt")

def check(r, c):
    ls = [False] * 10
    for i in range(9):  # 가로 방향 체크
        if arr[r][i]:
            ls[arr[r][i]] = True
    for i in range(9):  # 세로 방향 체크
        if arr[i][c]:
            ls[arr[i][c]] = True
    # 박스 체크
    r_ = r % 3
    c_ = c % 3
    for i in range(-r_, 3 - r_):
        for j in range(-c_, 3 - c_):
                if arr[r + i][c + j]:
                    ls[arr[r + i][c + j]] = True
    result = []
    for i in range(1, 10):
        if not ls[i]:
            result.append(i)
    return result

def solve(cur):
    if cur == m:
        for row in arr:
            print(*row)
        exit()

    cur_r, cur_c = blank[cur][0], blank[cur][1]
    candidate = check(cur_r, cur_c)
    for num in candidate:
        arr[cur_r][cur_c] = num
        solve(cur + 1)
        arr[cur_r][cur_c] = 0

arr = [list(map(int, input().split())) for _ in range(9)]
blank = []
for i in range(9):
    for j in range(9):
        if arr[i][j] == 0:
            blank.append((i, j))

m = len(blank)
solve(0)

풀이

백트래킹 문제에 대해 관심을 가졌을 때 가장 먼저 눌러보았던 문제였지만 많이 겁먹었어서 손조차 못 댔던 문제다 ㅎㅎ

최근에 백트래킹 문제들을 연습해보다가 이제 좀 풀 때 되지 않았나 해서 도전해 보았다.

비어있는 칸들을 리스트에 담은 후에 한칸 한칸 채우면서 풀이를 진행했었다.

처음 시간 초과가 났었을 때 뭐지? 했는데 바보같이 1~9 까지 전부 체크해서 채웠던 칸들을 비우고 다시 채우는 짓을 하고 있었다…ㅎ

정답 처리 후 다른 분들의 코드를 보았는데 시간을 많이 줄인건 너무 코드가 길고 복잡해보여서 패스.

적당히 긴 시간 중에서 나보다 짧은 것을 찾던 도중에 for 문을 1~9로 돌지 말고

빈칸에 들어갈 수 있는 숫자들을 먼저 구한 후 그 수들에 대해서만 dfs를 진행한 풀이들을 보았다.

내 방식대로 바꾸어서 제출해 보았는데 시간이 3분의 1로 줄었당!

골칫거리였던 스도쿠 문제를 해결해서 기쁘고 백트래킹에 대한 자신감?이 좀 생겼다 ㅎ