[백준] 2580 - 스도쿠 (Python)

문제 링크

알고리즘

• 백트래킹

백트래킹이란?

• 모든 경우의 수를 전부 고려하는 알고리즘
• 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. (나무 위키)
  
  
  구현 방식
  
  
• DFS(깊이 우선 탐색 / 스택 활용)
• BFS(너비 우선 탐색 / 큐 활용) (큐를 사용하지 않을 수도 있음)
• Best First Search(최선 우선 탐색 / 우선 순위 큐 활용)
  
  
  많은 블로그에서 백트래킹 == DFS 라고 하지만 상황에 따라 BFS로도 백트래킹을 구현할 수 있다.

Tip

• 모든 경우의 수를 탐색하는 것이 백트래킹이다.
• 분기가 추가될 때마다 현재 분기가 유망한지 검사 후 유망하지 않다면 분기를 종료한다.(가지치기)
  유망한지 검사하는 함수를 최적화하는 것이 중요
• 분기가 종료(반환)되면 다시 이전 상태로 돌려놓는다.

풀이

1. 스도쿠를 돌면서 빈자리(0)를 탐색한다
2. 빈자리에 1~9 를 넣었을 때 세로,가로,칸에 대해 각각 가능한지 (중복되는 숫자가 있는지) 테스트한다.
3. 가능하다면 스도쿠판에 숫자를 넣고 재귀함수를 호출하고 가능하지 않다면 함수를 반환한다.
4. 3번에서 만약 호출한 함수가 반환되면 숫자를 넣었던 자리에 0을 넣어서 스도쿠판을 복구한다.
5. 가능한 케이스가 발견되면 출력 후 프로그램을 종료한다 exit(0)

코드

python은 시간초과나서 pypy로 제출함

import sys

input = sys.stdin.readline


# 같은 행에 중복되는 숫자가 없는지
def check_row(row, n):
    for i in range(9):
        if n == sudoku[row][i]:
            return False
    return True


# 같은 열에 중복되는 숫자가 없는지
def check_col(col, n):
    for i in range(9):
        if n == sudoku[i][col]:
            return False
    return True


# 같은 칸에 중복되는 숫자가 없는지
def check_rect(row, col, n):
    # 각 칸이 시작하는 인덱스를 구함
    # 012 345 678
    # 2 -> 0
    # 5 -> 3
    real_row = row // 3 * 3
    real_col = col // 3 * 3
    for y in range(3):
        for x in range(3):
            if n == sudoku[real_row + y][real_col + x]:
                return False
    return True


sudoku = [[] for _ in range(9)]  # 스도쿠 판
empty_place = []  # 빈자리[(row,col)]

# 스도쿠판에 숫자 채우기 & 빈자리는 따로 리스트에 보관
for n in range(9):
    for m, num in enumerate([int(x) for x in input().split()]):
        sudoku[n].append(num)
        if num == 0:
            empty_place.append((n, m))


def dfs(n):
    if n == len(empty_place):
    	# 답을 찾으면 프로그램 종료
        for i in range(9):
            print(*sudoku[i])
        exit(0)
        
    # 빈자리에 1~9까지 넣어보고 가능하다면 재귀함수 호출
    row = empty_place[n][0]
    col = empty_place[n][1]
    for i in range(1, 10):
        if check_row(row, i) and check_col(col, i) and check_rect(row, col, i):
            sudoku[row][col] = i  # 1~9 숫자 넣고
            dfs(n + 1)  # 새로운 분기 시작
            sudoku[row][col] = 0  # 분기가 종료되면 (답이 없다면) 원상태 복구


dfs(0)

소감

함수가 반환되면 그 후에 다시 되돌려놓는 방식을 생각 못해서 분기마다 새 배열을 만들고 매개변수로 넘겨주고 있었다.
배열을 복사하는 과정에서 시간초과, 매 분기 복사된 배열 때문에 메모리 초과가 동시에 났다.
구글링 후 해결 방법을 봤을 때 정말 감탄스러웠고 앞으로 유용하게 써먹어야겠다.