Sign in Subscribe
PS

[PS] BOJ 4056 / 스-스-스도쿠

Minjun Kim

• 7 min read
[PS] BOJ 4056 / 스-스-스도쿠
문제 링크: https://www.acmicpc.net/problem/4056
Thumbnail: Photo by Luna Lee (Unsplash)

스도쿠를 풀어봅시다. 백트래킹으로요.

풀이

스도쿠의 규칙은 다음과 같습니다.

  • 같은 행에는 1~9까지의 수가 1개씩만 포함됩니다.
  • 같은 열에는 1~9까지의 수가 1개씩만 포함됩니다.
  • 같은 칸(3x3)에는 1~9까지의 수가 1개씩만 포함됩니다.

이 규칙을 기반으로, 백트래킹을 진행하면서 스도쿠를 채웁니다.

스도쿠 입력

문제 입력에 대해 주의해야 할 점이 몇가지 있습니다.

  • 항상 빈칸이 5개인 스도쿠만 입력으로 주어진다.
  • 잘못된 스도쿠 (숫자 중복) 또는 풀 수 없는 스도쿠가 주어질 수 있다.
  • 반드시 정답이 유일한 스도쿠만 입력으로 주어진다.

따라서, 백트래킹을 진행하기 전에 먼저 입력 받은 스도쿠 데이터를 검증해야 합니다.

sudoku = [[0 for _ in range(9)] for _ in range(9)]
rows = [[False for _ in range(10)] for _ in range(9)]
cols = [[False for _ in range(10)] for _ in range(9)]
grids = [[False for _ in range(10)] for _ in range(9)]
blanks = [None] * 5     # [(r, c)] 형태로 빈칸의 좌표를 저장한다.

def handle_input():
    """입력값을 읽어 sudoku, rows, cols, grids, blanks를 초기화합니다."""
    data = [input().strip() for _ in range(9)] # 반드시 입력을 모두 받아둬야 한다.
    
    # 스도쿠 입력 및 상태변수 갱신
    blank_cnt = 0
    for r in range(9):
        for c, v in enumerate(map(int, data[r])):
            sudoku[r][c] = v
            if v == 0:
                blanks[blank_cnt] = (r, c)
                blank_cnt += 1
            else:
                grids_idx = (r // 3) * 3 + (c // 3)
                if rows[r][v] or cols[c][v] or grids[grids_idx][v]:
                    return False  # 잘못된 입력 처리
                rows[r][v] = True
                cols[c][v] = True
                grids[grids_idx][v] = True

    return True

입력 데이터 검증하기

입력 데이터 검증시 주의할 것

이전에는 아래와 같이 입력 데이터를 검증했습니다. 위 코드와 차이점이라면, 입력을 미리 받지 않고 그때그때 받으면서 검사한 것인데, 만약 잘못된 입력이 발견될 경우 즉시 return되면서 이전 테스트 케이스의 입력 데이터가 다 처리되지 못하고 남아있게 됩니다.

이 경우, 남아 있는 입력 데이터로 인해 전체 입력이 밀려서 처리되어 정상적으로 동작하지 않게 됩니다. 따라서, 위 코드처럼 입력 데이터를 반드시 다 읽은 뒤 함수를 종료하도록 해야 합니다. 

sudoku = [[0 for _ in range(9)] for _ in range(9)]
rows = [[False for _ in range(10)] for _ in range(9)]
cols = [[False for _ in range(10)] for _ in range(9)]
grids = [[False for _ in range(10)] for _ in range(9)]
blanks = [None] * 5     # [(r, c)] 형태로 빈칸의 좌표를 저장한다.

def handle_input():
    """입력값을 읽어 sudoku, rows, cols, grids, blanks를 초기화합니다."""
    # 스도쿠 입력 및 상태변수 갱신
    blank_cnt = 0
    for r in range(9):
        for c, v in enumerate(map(int, input().strip())):
            sudoku[r][c] = v
            if v == 0:
                blanks[blank_cnt] = (r, c)
                blank_cnt += 1
            else:
                grids_idx = (r // 3) * 3 + (c // 3)
                if rows[r][v] or cols[c][v] or grids[grids_idx][v]:
                    return False  # 잘못된 입력 처리
                rows[r][v] = True
                cols[c][v] = True
                grids[grids_idx][v] = True

    return True

잘못된 입력 데이터 검증 방식

백트래킹으로 스도쿠 풀기

이제 백트래킹으로 입력 받은 스도쿠를 풀어야 합니다.

기본적인 풀이는 [PS] BOJ 2239 / 스도쿠와 유사하니, 자세한 설명은 이 글을 참고해주세요 😉

백트래킹을 통해 5개의 빈칸을 순서대로 채우는데, 언제나 정답이 유일한 스도쿠만 입력으로 주어지므로 정답을 찾는 즉시 탐색을 종료해도 됩니다.

이를 위해서, found라는 상태 변수를 도입해 백트래킹 전반에 적용했습니다. 또, 탐색 결과는 그 즉시 sudoku배열에 채우도록 해 불필요한 배열 사용을 줄였습니다.

def backtracking(depth):
    global found
    if found:   # 이미 정답을 찾았으므로 더 이상 탐색하지 않습니다.
        return

    if depth == 5:
        found = True
        return
    
    r, c = blanks[depth]
    grids_idx = (r // 3) * 3 + (c // 3)
    for v in range(1, 10):
        if not found and not rows[r][v] and not cols[c][v] and not grids[grids_idx][v]:
            # 분기 변수 설정
            rows[r][v] = True
            cols[c][v] = True
            grids[grids_idx][v] = True
            sudoku[r][c] = v
            # DFS (백트래킹)
            backtracking(depth + 1)
            if found:
                return
            # 분기 변수 초기화
            rows[r][v] = False
            cols[c][v] = False
            grids[grids_idx][v] = False
    sudoku[r][c] = 0

백트래킹으로 스도쿠 풀기

전체 테스트 케이스 처리

이 과정을 $T$개의 테스트 케이스에 대해 반복해야 합니다. 따라서, 매 테스트 케이스마다 상태 변수들을 초기화 해줘야 합니다. 또, 각 테스트 케이스의 답 사이에는 개행을 두고 출력해야 합니다.

for _ in range(int(input())):
    # 상태 변수 초기화
    found = False
    for idx in range(9):
        for number in range(1, 10):
            rows[idx][number] = False
            cols[idx][number] = False
            grids[idx][number] = False
    
    # 초기 입력 검증
    is_correct = handle_input()
    if not is_correct:
        print("Could not complete this grid.\n")
        continue

    # 백트래킹으로 스도쿠 풀기
    backtracking(0)

    # 정답에 따라 결과 처리하기
    if found:
        # 결과 출력하기
        print("\n".join("".join(map(str, row)) for row in sudoku))
    else:
        print("Could not complete this grid.")
    print()

전체 코드

input = open(0).readline

sudoku = [[0 for _ in range(9)] for _ in range(9)]
rows = [[False for _ in range(10)] for _ in range(9)]
cols = [[False for _ in range(10)] for _ in range(9)]
grids = [[False for _ in range(10)] for _ in range(9)]
blanks = [None] * 5     # [(r, c)] 형태로 빈칸의 좌표를 저장한다.

def handle_input():
    """입력값을 읽어 sudoku, rows, cols, grids, blanks를 초기화합니다."""
    blank_cnt = 0
    data = [input().strip() for _ in range(9)]
    
    # 스도쿠 입력 및 상태변수 갱신
    for r in range(9):
        for c, v in enumerate(map(int, data[r])):
            sudoku[r][c] = v
            if v == 0:
                blanks[blank_cnt] = (r, c)
                blank_cnt += 1
            else:
                grids_idx = (r // 3) * 3 + (c // 3)
                if rows[r][v] or cols[c][v] or grids[grids_idx][v]:
                    return False  # 잘못된 입력 처리
                rows[r][v] = True
                cols[c][v] = True
                grids[grids_idx][v] = True

    return True

def backtracking(depth):
    global found
    if found:   # 이미 정답을 찾았으므로 더 이상 탐색하지 않습니다.
        return

    if depth == 5:
        found = True
        return
    
    r, c = blanks[depth]
    grids_idx = (r // 3) * 3 + (c // 3)
    for v in range(1, 10):
        if not found and not rows[r][v] and not cols[c][v] and not grids[grids_idx][v]:
            # 분기 변수 설정
            rows[r][v] = True
            cols[c][v] = True
            grids[grids_idx][v] = True
            sudoku[r][c] = v
            # DFS (백트래킹)
            backtracking(depth + 1)
            if found:
                return
            # 분기 변수 초기화
            rows[r][v] = False
            cols[c][v] = False
            grids[grids_idx][v] = False
    sudoku[r][c] = 0

for _ in range(int(input())):
    # 상태 변수 초기화
    found = False
    for idx in range(9):
        for number in range(1, 10):
            rows[idx][number] = False
            cols[idx][number] = False
            grids[idx][number] = False
    
    # 초기 입력 검증
    is_correct = handle_input()
    if not is_correct:
        print("Could not complete this grid.\n")
        continue

    # 백트래킹으로 스도쿠 풀기
    backtracking(0)

    # 정답에 따라 결과 처리하기
    if found:
        # 결과 출력하기
        print("\n".join("".join(map(str, row)) for row in sudoku))
    else:
        print("Could not complete this grid.")
    print()

solution.py