[#2239] 스도쿠

RookieAND·2022년 12월 10일

DFS 백준 백트래킹 코테

BaekJoon

목록 보기

41/42

❓ Question

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

📖 Before Start

백트래킹 과 DFS 탐색 을 적절히 활용하여 푸는 문제.

이번 문제는 백트래킹 과 DFS 탐색 을 둘 다 활용하여 푸는 문제였다.
스도쿠 로직을 구현해본 것은 처음이었기에, 제법 인상 깊은 문제였다.

✒️ Design Algorithm

현재 좌표에 적절한 숫자를 집어넣고, 바로 옆에 있는 좌표를 탐색한다.

가로 9 칸, 세로 9 칸의 이차원 배열을 만들고 스도쿠 맞추기를 시작한다.
스도쿠 게임은 총 세 가지 규칙을 지켜서 모든 칸에 알맞은 숫자를 넣어야 한다.

현재 칸의 세로 줄에 1부터 9까지의 숫자가 모두 존재해야 한다.
현재 칸의 가로 줄에 1부터 9까지의 숫자가 모두 존재해야 한다.
스도쿠 영역을 3 X 3으로 나눈 영역 중, 현재 칸이 소속된 영역에 1부터 9까지의 숫자가 모두 존재해야 한다.

결국 이차원 배열을 모두 순회하면서, 각각의 칸에 조건에 맞는 숫자를 대입해야 했다.

💻 Making Own Code

✅ Correct Code

import sys

read = sys.stdin.readline
sudoku = [list(map(int, read().strip())) for _ in range(9)]

def check_sudoku(y, x, num):
    # 1번 (가로 줄) 의 조건이 유효한지 판별.
    for row in range(9):
        if sudoku[row][x] == num:
            return False
    # 2번 (세로 줄) 의 조건이 유효한지 판별
    for col in range(9):
        if sudoku[y][col] == num:
            return False
    # 3번 (3 x 3) 의 조건이 유효한지 판별
    for row in range(3):
        for col in range(3):
            if sudoku[(y // 3) * 3 + row][(x // 3) * 3 + col] == num:
                return False
    return True

# 탐색 순서 => 가로 줄 탐색 후 다음 세로 줄로 이동하는 방식.
def solve_sudoku(y, x):
    # 만약 스도쿠 탐색이 종료되었다면, 프로그램을 종료해야 함.
    if y == 9:
        for i in range(9):
            print(*sudoku[i], sep="")
        sys.exit(0)
    # 만약 현재 위치에 이미 숫자가 작성되었다면, 다음 위치로 패스해야 함.
    elif sudoku[y][x] > 0:
        solve_sudoku(y + ((x + 1) // 9), (x + 1) % 9)
    # 그렇지 않을 경우 1 ~ 10 까지 숫자를 대입하면서 계산 시작.
    else:
        for num in range(1, 10):
            # 숫자를 넣을 수 있는 경우, 이를 대입함.
            if check_sudoku(y, x, num):
                sudoku[y][x] = num
                solve_sudoku(y + ((x + 1) // 9), (x + 1) % 9)
                # 백 트래킹 과정
                sudoku[y][x] = 0

solve_sudoku(0, 0)

결국 이 문제는 백트래킹 알고리즘을 활용해야 해결이 가능했다

나는 문제를 풀기 전 하단에 기술된 로직을 세우고, 코드를 작성했다.

9 X 9 스도쿠 판을 하나의 이차원 배열로 놓고, 탐색은 (0, 0) 부터 시작한다.
탐색의 경우 가로 줄을 먼저 탐색하고, 이후 다음 세로 줄로 넘어가도록 한다.
만약 조건에 맞지 않는 케이스가 나올 경우, 백트래킹으로 이전 좌표를 검수한다.

이후 다른 분들의 풀이를 보다가, 0이 적힌 좌표 들을 별도로 모은 후에
이를 대상으로 DFS 탐색을 진행한 풀이 방식이 있어 이 또한 참고하였다.

import sys

read = sys.stdin.readline
sudoku, blank = [], []

# 스도쿠 판과 공백이 담긴 좌표 값을 선별하여 저장.
for row in range(9):
    sudoku.append(list(map(int, read().strip())))
    for col in range(9):
        if sudoku[row][col] == 0:
            blank.append((row, col))

def check_sudoku(y, x, num):
    # 1번 (가로 줄) 의 조건이 유효한지 판별.
    for row in range(9):
        if sudoku[row][x] == num:
            return False
    # 2번 (세로 줄) 의 조건이 유효한지 판별
    for col in range(9):
        if sudoku[y][col] == num:
            return False
    # 3번 (3 x 3) 의 조건이 유효한지 판별
    for row in range(3):
        for col in range(3):
            if sudoku[(y // 3) * 3 + row][(x // 3) * 3 + col] == num:
                return False
    return True

# 빈 칸이 담긴 좌표에 대한 탐색을 진행.
def solve_sudoku(idx):
    # 모든 빈칸에 대한 탐색이 종료되었다면, 프로그램을 종료해야 함.
    if idx == len(blank):
        for i in range(9):
            print(*sudoku[i], sep="")
        sys.exit(0)
    # 그렇지 않을 경우 1 ~ 10 까지 숫자를 대입하면서 계산 시작.
    ny, nx = blank[idx]
    for num in range(1, 10):
        if check_sudoku(ny, nx, num):
            # 숫자를 넣을 수 있는 경우, 이를 대입하고 다음 좌표 탐색
            sudoku[ny][nx] = num
            solve_sudoku(idx + 1)
            # 그렇지 않을 경우 값을 초기화 하여 이전의 좌표로 돌아감.
            sudoku[ny][nx] = 0

solve_sudoku(0)