[BOJ] 2239 스도쿠 | Python

문제

백준 2239번 스도쿠 | 골드4

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

2239번: 스도쿠

• 알고리즘 분류 : 구현 | 백트래킹

 

 

풀이 과정

파이썬 풀이

import sys
input = sys.stdin.readline

def row_check(row, num):   # 가로 확인
    for col in range(9):
        if arr[row][col] == num:
            # 넣을 값(num)이 이미 그 줄에 있으면 False
            return False
    return True

def col_check(col, num):    # 세로 확인
    for row in range(9):
        if arr[row][col] == num:
            return False
    return True

def square_check(row, col, num):    # 사각형 확인
    r = row // 3 * 3 
    c = col // 3 * 3
    # 각 사각형의 첫번째 행/렬로 설정(0, 3, 6 중 하나)

    for a in range(3):
        for b in range(3):
            if arr[r+a][c+b] == num:
                return False
    return True


def dfs(idx):
    if idx == len(zero_idx):
    	# 0인 값 다 채웠으면 프린트하고 함수 종료
        for i in range(9):
            for j in range(9):
                print(arr[i][j], end="")
            print()
        exit()

    x, y = zero_idx[idx]
    # 함수 호출될 때마다 해당 인덱스의 zero_idx 값 가져와야 함
    for n in range(1, 10):
        if row_check(x, n) and col_check(y, n) and square_check(x, y, n):
        # check 다 통과하면
            arr[x][y] = n
            dfs(idx+1)
            arr[x][y] = 0


# rstrip() 잊지 말기
arr = [list(map(int, input().rstrip())) for _ in range(9)]
zero_idx = []
for i in range(9):
    for j in range(9):
        if not arr[i][j]:
            zero_idx.append((i, j))

dfs(0)

 

• 0인 곳의 x, y좌표를 튜플 형태로 zero_idx라는 리스트에 저장
• 해당 자리에 대해 dfs 재귀함수를 통해 숫자 추가하기
  • 가로, 세로, 사각형 모두 확인해서 통과하면 숫자 넣기
  • idx+1하여 재귀 호출하여 그 다음 0인 좌표에 대해 탐색
  • 사각형 탐색할 때는 해당 좌표가 포함된 사각형의 좌측 상단부터 9칸 조사하는 게 편하므로
    0, 3, 6의 행/열에서부터 시작할 수 있도록 r, c 변수 할당
• `split()`으로 받지 않는 입력값이 오랜만이라 실수 있었다,, 주의하기!
• 메모리, 시간 줄일 수 있는 방법 고안해보기