[백준] 2239 스도쿠 (Python/파이썬)

<문제 링크>

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

2239번: 스도쿠

<풀이 전략>

1. 행 / 열 / 사각형에 대해 검증을 하면서 백트래킹을 하면 된다.

2. 사각형 영역에 대한 검증을 어떻게 할지가 조금 까다로운데 자세한 건 코드를 참고해보자

 

<정답 코드>

from collections import defaultdict
import sys, os, io, atexit

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

# 220921 2239 스도쿠

# 정답코드

# board: 스도쿠 배열 
N = 9
board = [list(map(int, input())) for _ in range(N)]


# find_square: 입력받은 좌표가 스도쿠에서 몇번쨰 사각형에 위치해있는지 반환해주는 함수 
def find_square(r, c):
    return (r // 3) * 3+ (c // 3)


# get_idx: 0-80사이의 숫자를 9x9 배열의 좌표로 변환해서 반환해주는 함수
def get_idx(num):
    r = num // 9
    c = num % 9
    return r, c


# 백트래킹으로 스도쿠 채워나가는 함수
def back_tracking(depth):

    # 마지막칸까지 스도쿠를 채웠을 경우
    if depth == 81:
        # 정답 출력 후 종료
        for i in board:
            print(''.join(map(str, i)))
        exit(0)

    # r, c 스도쿠 배열의 좌표
    r, c = get_idx(depth)

    # 숫자가 이미 채워져 있을 경우엔 바로 다음 좌표로 넘어간다.
    if board[r][c]:
        back_tracking(depth + 1)

    else:
        # 1-9 숫자 선택
        for num in numbers:
            # 행, 열, 사각형에 겹치는 숫자가 없을 경우
            if not visited_row[r][num] and not visited_col[c][num] and not visited_square[find_square(r, c)][num]:
                
                # 스도쿠 배열을 채워준다.
                board[r][c] = num
                # 행, 열, 사각형 방문 표시
                visited_row[r][num] = 1
                visited_col[c][num] = 1
                visited_square[find_square(r, c)][num] = 1

                # 다음 좌표 재귀적으로 탐색 
                back_tracking(depth + 1)

                # 백트래킹
                board[r][c] = 0
                visited_row[r][num] = 0
                visited_col[c][num] = 0
                visited_square[find_square(r, c)][num] = 0

        # 반복문을 다 돌았는데 조건에 맞는 숫자를 넣을 수 없는 경우 반환
        else:
            return


# numbers: 스도쿠에 채워 넣을 숫자들
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
# 행, 열, 사각형에 대한 방문여부 표시 배열
visited_row = [[0 for _ in range(10)] for _ in range(10)]
visited_col = [[0 for _ in range(10)] for _ in range(10)]
visited_square = [[0 for _ in range(10)] for _ in range(10)]

# 주어진 배열 기반으로 visited 배열 채워 넣기
for r in range(9):
    for c in range(9):
        if board[r][c]:
            visited_row[r][board[r][c]] = 1
            visited_col[c][board[r][c]] = 1
            visited_square[find_square(r, c)][board[r][c]] = 1

# 첫번쨰 칸부터 스도쿠 채워나가기
back_tracking(0)