[Python | 2580] 스도쿠

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

---

문제 설명

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

 

📌 시간 제한: 1초

---

입력

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

---

출력

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

---

문제 접근

스도쿠는 9×9 보드에 1부터 9까지의 숫자를 채워 넣는 퍼즐이다. 규칙은 다음과 같다:

• 각 행과 각 열에는 1부터 9까지의 숫자가 중복 없이 한 번씩만 등장해야 한다.
• 각 3×3 정사각형(총 9개 영역)에도 1부터 9까지의 숫자가 중복 없이 들어가야 한다.

이 문제에서는 일부 칸이 비어 있는 상태(숫자 0으로 표시됨)에서 시작하며, 이를 규칙에 맞게 모두 채워서 스도쿠를 완성하는 것이 목표다. 이 문제는 항상 하나의 유일한 정답만 존재함이 보장된다.

 

이 문제는 전형적인 DFS 기반의 탐색 문제다. 왜 DFS(Depth-First Search) 방식이 적합한지 생각해보자. 빈 칸이 여러 개 있을 때, 각 칸마다 1부터 9까지 가능한 숫자를 넣어가며 깊이 우선으로 탐색하게 되면, 한 가지 숫자 조합을 끝까지 시도하여 최종 완성 상태에 도달할 수 있다. 이 과정에서 조건을 만족하지 않는 경우가 나오면, 해당 경로는 더 이상 볼 필요 없이 되돌아가 다른 숫자를 시도할 수 있다. 이처럼 가능한 경로를 깊이 따라가며 탐색하고, 조건을 만족하지 않으면 되돌아가는 과정은 DFS의 작동 방식과 정확히 들어맞는다.

 

구현 절차

해결을 위해 거쳐야 할 단계는 다음과 같다:

1. 보드에서 빈 칸의 위치를 모두 찾아 리스트에 저장한다.
2. 각 빈 칸에 대해 1부터 9까지의 숫자를 시도한다.
3. 숫자를 넣었을 때 현재 스도쿠 보드 상태가 유효하다면 다음 빈 칸으로 넘어간다.
4. 만약 어떤 시점에서 더 이상 채울 수 없는 경우가 발생하면, 직전 단계로 되돌아가 다른 숫자를 시도한다. 이것이 백트래킹이다.
5. 빈 칸을 모두 채운 경우, 즉 재귀의 깊이가 빈 칸 수와 같아진 경우에는 정답이 완성된 것이다.

여기서 주요 구현 포인트는

• 유효성 검사: 숫자를 넣기 전에 해당 숫자가 현재 행, 열, 3×3 사각형 안에 이미 존재하지 않는지 확인한다.
• 3×3 정사각형 구간 계산: (x, y) 좌표에 대해 해당 구간의 시작점은 (x // 3 * 3, y // 3 * 3) 이다.
• 정답이 여러 개일 수 없으므로 첫 번째 정답을 출력한 뒤 프로그램을 종료한다.

 

시간복잡도

이 알고리즘의 시간 복잡도는 최악의 경우 O(9^M)이다.
여기서 M은 빈 칸의 개수를 의미하며, 각 빈 칸마다 최대 9개의 숫자 후보를 탐색할 수 있기 때문이다.
이론상 9^81에 가까운 경우의 수가 존재할 수 있지만, 실제로는 유효성 검사를 통해 대부분의 가지가 중간에 잘리므로 탐색 공간은 급격히 줄어들게 된다. 따라서 현실적인 실행 시간은 매우 빠르며, 백준 시스템에서도 무리 없이 통과된다.

---

구현

구현 1

• 같은 행 검사: board[x][i] == num
  → 행 x의 i열에 이미 num이 있는지 확인
• 같은 열 검사: board[i][y] == num
  → 열 y의 i행에 이미 num이 있는지 확인
• 3×3 정사각형 검사:
  • 시작 좌표: x // 3 * 3, y // 3 * 3
  • 3×3 범위를 순회하며 해당 블록 내 중복 여부 확인

하나의 함수에서 세 조건을 한 번에 검사하는 구조
→ 코드가 간결하고 효율적이며, 재귀에서 수차례 호출되는 함수이므로 성능도 좋다.

import sys
input = sys.stdin.readline

# 9x9 스도쿠 판 입력
board = [list(map(int, input().split())) for _ in range(9)]

# 빈 칸의 좌표 수집
empties = [(i, j) for i in range(9) for j in range(9) if board[i][j] == 0]

def is_valid(x, y, num):
    # 행과 열에 num이 존재하는지 확인
    for i in range(9):
        if board[x][i] == num or board[i][y] == num:
            return False

    # 3x3 정사각형 확인
    start_x, start_y = x // 3 * 3, y // 3 * 3
    for i in range(3):
        for j in range(3):
            if board[start_x + i][start_y + j] == num:
                return False

    return True

def dfs(index):
    if index == len(empties):  # 모든 빈 칸을 채운 경우
        for row in board:
            print(' '.join(map(str, row)))
        sys.exit(0)

    x, y = empties[index]
    for num in range(1, 10):
        if is_valid(x, y, num):
            board[x][y] = num
            dfs(index + 1)
            board[x][y] = 0  # 백트래킹

dfs(0)

 

구현 2

스도쿠 규칙을 검사할 때, 행 / 열 / 3×3 정사각형을 각각 따로 검사하는 함수를 만들어 전체 유효성 검사를 조합식으로 구성할 수도 있다.

import sys
input = sys.stdin.readline

# 9x9 스도쿠 판 입력
board = [list(map(int, input().split())) for _ in range(9)]

# 빈 칸의 좌표 수집
empties = [(i, j) for i in range(9) for j in range(9) if board[i][j] == 0]

# 같은 행에 num이 존재하는지 확인
def check_row(x, num):
    for i in range(9):
        if board[x][i] == num:
            return False
    return True

# 같은 열에 num이 존재하는지 확인
def check_col(y, num):
    for i in range(9):
        if board[i][y] == num:
            return False
    return True

# 3x3 정사각형에 num이 존재하는지 확인
def check_square(x, y, num):
    start_x, start_y = x // 3 * 3, y // 3 * 3
    for i in range(3):
        for j in range(3):
            if board[start_x + i][start_y + j] == num:
                return False
    return True

# 위 세 가지를 모두 만족하면 유효한 숫자
def is_valid(x, y, num):
    return check_row(x, num) and check_col(y, num) and check_square(x, y, num)

def dfs(index):
    if index == len(empties):  # 모든 빈 칸을 채운 경우
        for row in board:
            print(' '.join(map(str, row)))
        sys.exit(0)

    x, y = empties[index]
    for num in range(1, 10):
        if is_valid(x, y, num):
            board[x][y] = num
            dfs(index + 1)
            board[x][y] = 0  # 백트래킹

dfs(0)