[백준 2580] 스도쿠 (파이썬)

문제

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

2580번: 스도쿠

---

풀이

# 83% 시간초과
# pypy 통과
import sys
input = sys.stdin.readline
from collections import deque

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

for row in range(9):
    for col in range(9):
        if graph[row][col] == 0:
            blanks.append((row, col))

def backTracking(cnt):
    global graph

    if cnt == len(blanks): # 빈칸이 없는 경우 끝
        for row in graph:
            print(*row)
        exit(0)
    
    row, col = blanks[cnt]
    for i in range(1, 10):
        if check(i, row, col):
            graph[row][col] = i
            backTracking(cnt + 1)
            graph[row][col] = 0
    
def check(num, row, col):
    # 같은 행에 해당 숫자 있음
    if num in graph[row]: 
        return False
    
    # 같은 열에 해당 숫자 있음
    for row_ in graph:
        if row_[col] == num:
            return False
        
    # 33 블럭 안에 해당 숫자 있음
    checkRow = (row // 3) * 3
    checkCol = (col // 3) * 3
    
    for row_ in graph[checkRow: checkRow+3]:
        for item in row_[checkCol: checkCol+3]:
            if item == num:
                return False
    
    return True 

backTracking(0)

 

---

문제 설명

백 트래킹 유형의 문제이다. 백 트래킹은 현재의 선택이 다음 선택에 영향을 미치는 문제에서 많이 사용된다. 특히, 그러한 선택으로 가능한 경우의 수를 묻는 문제를 많이 낸다. 그러므로 "경우의 수"를 묻는 문제면 일단 백 트래킹을 떠올리자!
해당 문제는 성립하는 완성된 스도쿠를 출력하는 것으로 주었다. 만약 완성될 수 있는 스도쿠의 경우의 수를 묻는 다면 완전히 백 트래킹을 저격한 문제였을 것이다. 그래도 선택한 빈칸의 숫자가 다음 빈칸의 숫자에 영향을 주는 것을 보고 백 트래킹을 떠올려야 할 것이다.

백 트래킹의 기본적인 구조이다.

parm을 무엇으로 할지는 문제 상황마다 개발자 성향만다 다르다. 위 경우는 parm이 배열인 상황인데 이렇게 구현하면 쉽게 될때도 많지만 "시간 초과"에 걸리는 경우도 많다. 따라서 배열보다는 int 와 같은 자료형으로 처리 할 수 있게 구조를 짜는 연습을 하는 것이 좋다.

복잡한 문제일 수록 "특정 조건"을 복잡하게 하는 경우가 많다. 그래서 많은 경우 함수를 통해 따로 구현한다.

---

문제 KEY POINT

return vs exit(0)

백트래킹은 보통 parm이 "조건"을 만족하면 return 을하여 경우의 수를 세는 경우가 많다.
하지만 "스도쿠" 문제의 경우 경우의 수를 세는 것이 아닌 만족하는 한 가지 스도쿠가 나오는 순간 멈춰야 한다.
따라서 return 이 아닌 exit(0)을 사용했다. exit(0)을 사용하면 프로세스 전체가 종료 된다.