[Python / BOJ 2239] 스토쿠

 

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

2239번: 스도쿠

 

 

 

0. 문제

위와 같이 9x9 크기의 스도쿠가 있으며, 당신에게는 하다 만 스도쿠가 주어진다. 스도쿠를 해결하라.

• 채워져 있지 않은 칸은 0으로 주어진다.
• 답이 여러 개면 사전 순으로 앞서는 것을 출력하라.

 

 

 

 

1. 아이디어

1. 백트래킹 문제. (특별히 뭔가 생각나는 게 없으면 완전 탐색으로 푼다)
2. 채워져 있지 않은 칸에 넣을 숫자를 생각한다. 단순히 1~9까지 모두 고려해보는 것으로 충분하다
   • 가로줄, 세로줄, 3x3 영역에서 겹치는 숫자가 없어야 한다. check 함수를 만들어 이를 확인한다.
   • 모든 경우의 수를 보기에 오래 걸리지 않을까 싶었는데, 위 제한이 상당해서 괜찮은 듯
3. 특정 칸에 넣을 숫자를 정했으면 다음 칸을 확인하고 동일하게 반복한다.
   
   • 사전 순으로 앞서는 것을 출력해야 하기 때문에 오른쪽, 아래 방향으로 탐색한다.
   • (r, c)좌표는 num // row길이, num % col길이 로 표현할 수 있다.
4. 답이 여러 개일 때 제일 먼저 만나는 하나만 출력해야 하므로 답을 찾으면 exit()로 바로 종료한다.

 

 

 

 

 

2. 구현

def check(r, c, value):
    # 가로 줄에 value가 있는지 확인
    if value in IN[r]:
        return False
    # 세로 줄에 value가 있는지 확인
    if value in map(lambda x: x[c], IN):
        return False
    # 3x3 정사각형에 value가 있는지 확인
    unit_r, unit_c = 3 * (r // 3), 3 * (c // 3)
    for i in range(unit_r, unit_r + 3):
        for j in range(unit_c, unit_c + 3):
            if value == IN[i][j]:
                return False
    return True


def func(num):
    # 마지막 칸이면 답 출력하고 종료
    if num == 81:
        for r in range(9):
            print(''.join(map(str, IN[r])))
        exit()

    r, c = num // 9, num % 9
    # 숫자가 채워져 있으면 넘어가기
    if IN[r][c]:
        func(num + 1)
    # 숫자가 채워져 있지 않으면
    else:
        for n in range(1, 10):
            # 숫자 n이 유효한지 확인해서 유효하면 숫자 입력
            if check(r, c, n):
                IN[r][c] = n
                func(num + 1)
                IN[r][c] = 0

IN = [list(map(int, list(input()))) for _ in range(9)]
func(0)