[백준][20단계 백트래킹] 2580번 /스도쿠 (파이썬/Python)

1. 문제 설명

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

2. 코드

import sys
sys.setrecursionlimit(10000)

# ----- 입력 -----
nums = list(map(int, sys.stdin.read().split()))
board = [nums[i*9:(i+1)*9] for i in range(9)]

# ----- 사용 여부 테이블 -----
row_used = [[False]*10 for _ in range(9)]
col_used = [[False]*10 for _ in range(9)]
box_used = [[False]*10 for _ in range(9)]

def box_id(r, c):
    return (r//3)*3 + (c//3)

for r in range(9):
    for c in range(9):
        d = board[r][c]
        if d:
            row_used[r][d] = True
            col_used[c][d] = True
            box_used[box_id(r, c)][d] = True

# 빈 칸 목록(한 번만 생성)
empties = [(r, c) for r in range(9) for c in range(9) if board[r][c] == 0]

# ----- 후보가 가장 적은 칸 선택(MRV) -----
def pick_mrv(start_idx: int):
    best_i = -1
    best_cnt = 10
    best_cands = None
    for i in range(start_idx, len(empties)):
        r, c = empties[i]
        if board[r][c] != 0:
            continue
        b = box_id(r, c)
        cands = []
        # 1~9 중 가능한 것 수집
        for d in range(1, 10):
            if not row_used[r][d] and not col_used[c][d] and not box_used[b][d]:
                cands.append(d)
        cnt = len(cands)
        if cnt == 0:
            return i, []  # 바로 백트래킹
        if cnt < best_cnt:
            best_cnt = cnt
            best_i = i
            best_cands = cands
            if cnt == 1:  # 더 찾을 필요 없음
                break
    return best_i, best_cands

# ----- 백트래킹 -----
def dfs(depth: int) -> bool:
    if depth == len(empties):
        return True

    sel, cands = pick_mrv(depth)
    if sel == -1:
        return True
    if not cands:
        return False

    # 깊이 위치와 선택 위치를 스왑하여 "현재 깊이에서 채울 칸"을 고정
    empties[depth], empties[sel] = empties[sel], empties[depth]
    r, c = empties[depth]
    b = box_id(r, c)

    for d in cands:
        # 배치
        board[r][c] = d
        row_used[r][d] = col_used[c][d] = box_used[b][d] = True

        if dfs(depth + 1):
            return True

        # 되돌리기
        board[r][c] = 0
        row_used[r][d] = col_used[c][d] = box_used[b][d] = False

    # 스왑 복구
    empties[depth], empties[sel] = empties[sel], empties[depth]
    return False

dfs(0)

# ----- 출력 -----
for r in range(9):
    print(*board[r])

3. 풀이 과정

스도쿠 문제를 해결하기 위해서는 먼저 숫자들을 행렬로 구분해서 저장시킨다.

모든 숫자들을 리스트로 저장하고 9개씩 잘라서 9개의 리스트로 나누었다.

그 다음은 넣어야 될 숫자들을 체크하기 위한 리스트를 만든다.

행, 열, 박스로 총 세 가지로 나누어서 10개의 [False]칸으로 9줄을 저장한다.

각 자리는 0부터 9까지의 숫자를 의미하고, 0은 빈칸을 의미한다.

그 다음은 리스트에 저장된 숫자들을 확인해서 행, 열 ,박스에 해당하는 자리를 True로 바꾼다.

0을 가진 위치들만 따로 저장해둔다.

 

이제 각 빈칸의 위치를 하나씩 확인하면서, 후보 수가 가장 적은 칸(MRV)를 찾아야 한다.

아직 안 채운 빈 칸들 중 그 칸에 들어갈 수 있는 숫자 목록을 계산하고, 후보가 0개면 실패 신호 반환하고, 1개면 그 칸을 고른다.

그 외에는 가장 적은 숫자의 칸을 선택한다.

 

이제 백트래킹(DFS)를 진행한다.

모든 빈 칸을 채웠다면 True

아니면, 그 칸을 현재 깊이의 자리로 고정한다.

후보들을 하나씩 시도한다.

보드에 숫자를 배치하고, 행, 열, 박스를 True로 바꿔가며 그 다음을 진행한다.

성공하면 True로 반환하고 실패면 배치를 되돌린다.

전부 실패하면 False로 반환한다.

4. 자투리 개념

• 백트래킹 알고리즘
  - 정답을 구성해 가는 중간 단계들을 체계적으로 탐색하되, 불필요한 가지는 일찍 잘라내는(Pruning) 깊이우선탐색(DFS)

핵심 아이디어

• 문제의 해 공간(Search Space):
  가능한 모든 해(또는 부분해)를 트리 형태로 생각합니다. 루트는 “아무 것도 선택하지 않음”, 깊이 d는 “d개 선택 완료”.
• 부분해(Partial Solution):
  아직 완성은 아니지만 제약을 만족하며 확장될 수 있는 중간 상태.
• DFS + 되돌리기(Backtrack):
  하나를 선택(choose) → 더 내려가서 탐색(explore) → 돌아오며 선택을 취소(unchoose)합니다.
• 가지치기(Pruning):
  제약을 위반하거나, 더 진행해도 정답이 절대 나오지 않을 “가지”는 즉시 탐색을 멈춥니다.

공통 템플릿

def backtrack(state):
    if 완성조건(state):
        정답 처리
        return

    for candidate in 후보집합(state):  # 보통 정렬/오름차순으로 순회
        if 제약을 만족(candidate, state):  # 가지치기 1차
            state에 candidate를 반영(choose)
            backtrack(state)
            state에서 candidate를 되돌리기(unchoose)  # 핵심