[BOJ] 2580번: 스도쿠

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

2580번: 스도쿠

 

문제풀이

스도쿠를 해결하기 위해 백트랙킹 알고리즘을 사용해야하는 것까지는 떠올리기 쉬웠지만, dfs를 어떤 방식으로 적용할지 생각해내는 것이 어려웠다. 우선 가장 기본적인 생각은 수를 채워야하는 칸의 행, 열, 정사각형 안에서 필요한 수를 찾는 것이다. 후보가 한개의 수만 존재한다면 단순히 값을 집어넣어주면 되지만 여러개라면 어떻게 할지 생각해야 했다. 그래서 생각한 방식이 우선 후보수 중에 하나의 수를 넣어주고 이 값으로 계속 수도쿠 풀이를 진행했을 때 옳지 않은 수였다는 것을 알게되면 다시 돌아가서 다른 후보수를 넣어주면 된다. 여기서 dfs 방식이 사용된다.

 

백준 문제에서 주어진 예로 생각을 해보았다.

수도쿠

수도쿠 풀이는 다음의 방식으로 진행된다. 여기서 idx는 빈칸만을 리스트로 만들었다고 생각했을 때의 인덱스이며 {}괄호 안의 수는 후보수 이다. 후보수는 해당 칸의 행, 열, 정사각형 안에서 1-9까지의 수 중 없는 수로 채택한다.

Python3 풀이

import sys

sudoku = []
for i in range(9):
    sudoku.append(list(map(int, sys.stdin.readline().split())))
zeros = [(i, j) for i in range(9) for j in range(9) if sudoku[i][j] == 0]

• 수도쿠 문제를 2차원 배열로 입력받은 후 0값이 들어있는 칸들의 위치를 리스트로 만든다. 

def find(row, col):
    missing_numbers=[1, 2, 3, 4, 5, 6, 7, 8, 9]
    for k in range(9):
        if sudoku[row][k] in missing_numbers:
            missing_numbers.remove(sudoku[row][k])
        if sudoku[k][col] in missing_numbers:
            missing_numbers.remove(sudoku[k][col])
    r_str = row//3 * 3
    c_str = col//3 * 3
    for i in range(r_str, r_str+3):
        for j in range(c_str, c_str+3):
            if sudoku[i][j] in missing_numbers:
                missing_numbers.remove(sudoku[i][j])
    return missing_numbers

 

• row, col의 위치가 주어졌을 때 해당 위치의 후보 수를 구한다.
• 1-9까지의 수로 리스트를 만들어 두고 해당 행과 열에서 존재하는 수를 제거한다.
• 해당 위치에 포함되는 3*3 정사각형 안에서 존재하는 수를 제거한다.
• 리스트의 남은 수들이 후보수가 되며 이를 반환한다.

def dfs(idx):
    if idx == len(zeros):
        for row in sudoku:
            print(*row)
        exit()

    else:
        row, col = zeros[idx]
        missing = find(row, col)
        for number in missing:
            sudoku[row][col] = number
            dfs(idx+1)
            sudoku[row][col] = 0

• 인자로 주어지는 인덱스는 0값이 채워져있던 위치를 담아둔 리스트인 zeros의 인덱스이다.
• 해당 인덱스가 0값이 채워진 칸의 개수에 도달했다면 이는 수도쿠를 다 채운 것으로 출력 후 종료한다.
• 아니라면 해당 인덱스의 행, 열 위치값을 얻고 후보수들을 얻는다. 해당 후보수 중 하나를 꺼내 해당 칸의 값을 채우고 다음 0값의 칸으로 이동한다.  만약 잘못된 값이 채워졌다면, dfs가 반복되다가 어느순간 후보수가 없어지게 된다. 이때 dfs가 반환되면서 해당 칸의 값을 다시 0으로 돌려놓는다.

dfs(0)

• 마지막은 dfs를 0번째 인덱스부터 실행!

 

Python3 Code

import sys

sudoku = []
for i in range(9):
    sudoku.append(list(map(int, sys.stdin.readline().split())))
zeros = [(i, j) for i in range(9) for j in range(9) if sudoku[i][j] == 0]


def find(row, col):
    missing_numbers=[1, 2, 3, 4, 5, 6, 7, 8, 9]
    for k in range(9):
        if sudoku[row][k] in missing_numbers:
            missing_numbers.remove(sudoku[row][k])
        if sudoku[k][col] in missing_numbers:
            missing_numbers.remove(sudoku[k][col])
    r_str = row//3 * 3
    c_str = col//3 * 3
    for i in range(r_str, r_str+3):
        for j in range(c_str, c_str+3):
            if sudoku[i][j] in missing_numbers:
                missing_numbers.remove(sudoku[i][j])
    return missing_numbers


def dfs(idx):
    if idx == len(zeros):
        for row in sudoku:
            print(*row)
        exit()

    else:
        row, col = zeros[idx]
        missing = find(row, col)
        for number in missing:
            sudoku[row][col] = number
            dfs(idx+1)
            sudoku[row][col] = 0


dfs(0)

백준에서 코드 제출 시에 파이썬3로 제출하면 시간초과가 나기때문에 PyPy3로 제출하였다.