2580. 스도쿠 (Python)

2580번: 스도쿠

 

풀이

 백트래킹을 사용하여 문제를 해결할 수 있다. 풀이 과정은 다음과 같다.

 

1. 먼저 입력을 받으면서 0이 들어있는 좌표를 리스트에 담아둔다. 
2. 첫 번째 0부터 시작하여 1~9까지의 숫자를 넣어본다. 이때 가로, 세로 그리고 사각형에 해당 숫자가 들어있는지를 체크한다.
3. 숫자를 넣을 수 있다면 이제 다음 0이 들어있는 좌표로 이동하여 똑같은 과정을 반복한다.
4. 0이 들어있는 모든 좌표에 숫자를 넣었다면 출력을 해주고 프로그램을 종료한다.

 

코드

import sys


# 백트래킹
def solve(idx):
    if idx == zeroCnt:  # 0이 들어있는 모든 좌표에 숫자를 넣었다면
        for i in range(9):  # 보드를 출력한다.
            print(" ".join(map(str, board[i])))
        sys.exit(0)  # 그 후 프로그램을 종료시킨다.

    row, col = zeroList[idx]  # 현재 0이 들어있는 행과 열
    rowStart = (row // 3) * 3  # 3x3 정사각형의 시작 행과 열을 구한다.
    colStart = (col // 3) * 3

    for num in range(1, 10):  # 1 ~ 9까지의 숫자를 차례대로 넣어본다.
        flag = True  # 숫자를 현재 좌표에 넣을 수 있는지를 판단하기 위한 플래그

        for i in range(9):
            if board[row][i] == num:  # 행 체크
                flag = False

            if board[i][col] == num:  # 열 체크
                flag = False

            # 3x3 정사각형 체크
            if board[rowStart + (i // 3)][colStart + (i % 3)] == num:
                flag = False

            if not flag:  # num 숫자를 현재 위치에 넣을 수 없다면 for문 종료
                break

        if flag:  # num 숫자를 넣을 수 있다면 채워넣고 다음 좌표로 넘어간다.
            board[row][col] = num
            solve(idx + 1)
            board[row][col] = 0


if __name__ == '__main__':
    board = [[0 for _ in range(9)] for _ in range(9)]
    zeroCnt = 0  # 0이 들어있는 좌표의 개수
    zeroList = []  # 0이 들어있는 좌표 정보를 담아두는 리스트. (행, 열)

    for i in range(9):
        tmp = list(map(int, input().split()))
        for j in range(9):
            if tmp[j] == 0:
                zeroCnt += 1
                zeroList.append((i, j))
            board[i][j] = tmp[j]

    solve(0)  # 0이 들어있는 좌표 중 첫 번째 좌표부터 시작