122. 2580(스도쿠)

이 코드는 pypy3에서 돌려야 시간초과가 발생하지 않습니다.

import sys
input = sys.stdin.readline

sudoku = [list(map(int, input().split())) for _ in range(9)]


def search(row, col, value):

    for i in range(9):
        if sudoku[row][i] == value:
            return False

    for i in range(9):
        if sudoku[i][col] == value:
            return False

    rowFirst = (row // 3) * 3
    colFirst = (col // 3) * 3

    for i in range(rowFirst, rowFirst+3):
        for j in range(colFirst, colFirst+3):
            if sudoku[i][j] == value:
                return False

    return True


def DFS(row, col):
    if col == 9:
        DFS(row+1, 0)
        return

    if row == 9:
        for val in sudoku:
            print(" ".join(map(str, val)))
        exit()


    if(sudoku[row][col] == 0):
        for i in range(1, 10):
            if(search(row, col, i)):
                sudoku[row][col] = i
                DFS(row, col+1)

        sudoku[row][col] = 0
        return

    DFS(row, col+1)


DFS(0, 0)

문제요약

스도쿠가 주어졌을 때 백트래킹을 이용하여 해결해보시오

설명

사실 차근차근해보면 문제가 크게 어렵지 않다.

아래 판이 주어지면 위와같이 만들면 된다.

 

스도쿠를 해결하는 단계는 다음과 같다.

---

search

1. 행에서 열의 요소를 탐색한다.

def search(row, col, value):
    # 1. 행의 열 탐색
    for i in range(9):
        if sudoku[row][i] == value:
            return False
    return True

2. 열에서 행의 요소를 탐색한다.

def search(row, col, value):
# 2. 열의 행 탐색
    for i in range(9):
        if sudoku[i][col] == value:
            return False
    return True

3. 작은 사각형 탐색

def search(row, col, value):
# 3. 작은 사각형 탐색
    rowFirst = (row // 3) * 3
    colFirst = (col // 3) * 3

    for i in range(rowFirst, rowFirst+3):
        for j in range(colFirst, colFirst+3):
            if sudoku[i][j] == value:
                return False
    return True

작은 삼각형의 첫위치는 rowFirst와 colFirst를 통해 정해준다.

 

 

위와같이 3가지의 경우를 search 하여 만약 하나라도 조건에 부합하다면 False (그 값이 아님) 를 반환하고 전부 통과한다면(그 값이 맞음) True를 반환한다.

def search(row, col, value):
    # 1. 행의 열 탐색
    for i in range(9):
        if sudoku[row][i] == value:
            return False

    # 2. 열의 행 탐색
    for i in range(9):
        if sudoku[i][col] == value:
            return False
    
    # 3. 작은 사각형 탐색
    rowFirst = (row // 3) * 3
    colFirst = (col // 3) * 3
    
    for i in range(rowFirst, rowFirst+3):
        for j in range(colFirst, colFirst+3):
            if sudoku[i][j] == value:
                return False

    return True

 

---

DFS

Search를 구현했으면 다음에는 깊이 우선 탐색을 통해 하나하나 비교해 나간다.

 

def DFS(row, col):
    # 열이 9일 경우 행을 일 증가시키고 열은 초기화
    if col == 9:
        DFS(row+1, 0)
        return

    # 행이 9일 경우 전부 탐색함. => 종료
    if row == 9:
        for val in sudoku:
            print(" ".join(map(str, val)))
        exit()

열의 수가 9에 도달한다면 열은 탐색이 끝난것이다.

따라서 행을 1증가시켜주고 열을 0으로 초기화 해서 1행을 탐색하기 시작한다.

 

행까지 9가 된다면 모든 위치를 탐색을 마친것으로 결과값을 출력하고 exit를 통해서 프로그램을 종료해준다.

 

# 0인 녀어석을 만났을 경우
    if(sudoku[row][col] == 0):
        # 숫자는 0~9
        for i in range(1, 10):
            if(search(row, col, i)):
                sudoku[row][col] = i
                DFS(row, col+1)
        # for을 다 돌았지만 조건에 다 부합할 경우
        sudoku[row][col] = 0
        return

    DFS(row, col+1)

0인 녀석이 나왔을 경우 (0이 빈칸이다.) 탐색을 시작해야한다.

숫자는 1~9까지 나올 것이다.

따라서 1~9를 반복문을 통해 반복을 해준다.

search를 통해 행,열,값을 넘겨주고, 만약 search 함수에서 모든 결과에 부합(일치하는 수가 없다) 그 수는 정답이므로 sudoku에 저장해준다.

 

해당 위치는 작업이 끝났으므로 열을 +1하여 다음 위치로 넘어간다.

 

sudoku[row][col] = 0
        return

이 구문은 0인 녀어석을 만났지만 1~9가 모두 부합할 수도 있다.

그 경우에 0인 녀어석을 다시 0으로 초기화 해주어야 한다.

 

    DFS(row, col+1)

마지막으로  0이 아닌경우 다음 열로 넘어가 탐색을 시작한다.