[백준] 스도쿠

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

2239번: 스도쿠

dfs를 이용하는 문제입니다. 

 

우선 문제부터 간단하게 요약하면, 하다 만 스도쿠가 input으로 들어오면, 마저 끝내서 return을 해야 하는 문제입니다.

 

처음에는 시간초과가 나왔습니다. 처음 풀이 아이디어와, 나중에 어떻게 고치는지 순서로 설명을 해보겠습니다.

 

<Solution>

우선 이 문제를 보면, dfs를 사용해야 하는 것을 알 수 있습니다. 간단한 예시를 통해 아이디어를 살펴봅시다. 

<idea>

다음 그림과 같이 0인 부분에 대해 후보를 조사합니다. 가로, 세로, 네모칸에 공통으로 들어가 있지 않은 수가 후보가 될 수 있습니다.

 

만약 후보가 [4,6] 이 나온다고 생각해봅시다. 그렇다면 이중 작은 4를 먼저 넣고 다음 0에 대해 후보를 또 조사합니다. 이 때, 후보가 [1,2,3] 이 나온다고 하면, 이중에서 1을 넣고 계속 이 과정을 끝날때 까지 반복합니다. 

 

만약 위의 예시에서 다음 0을 하는 도중 불가능 하다는 것을 1이 불가능 하다는 것을 알게 되면, 되돌아와서 2를 해봅니다. 만약 1,2,3이 모두 안되는 것을 알게 되면, 첫번째 구한 [4,6]의 후보중 6에 대해 조사합니다. 

 

이처럼 dfs 과정을 통해 문제를 해결할 수 있습니다. 

처음에는 이 candidate를 구하는 과정을 매번 새로 찾도록 만들었는데, 그렇게 하니 시간초과가 나왔습니다.

[시간초과가 발생한 코드]

import sys


sudoku = [list(map(int,list(sys.stdin.readline().rstrip()))) for _ in range(9)]

def find_candidate(sudoku, r, c):
    candidate = set(range(1,10))
    remove_candidate = set()
    # search row
    for i in range(9):
        if sudoku[r][i] != 0:
            remove_candidate.add(sudoku[r][i])
    # search column
    for i in range(9):
        if sudoku[i][c] != 0:
            remove_candidate.add(sudoku[i][c])
    # search box
    # find which box 
    '''
    0 1 2
    3 4 5
    6 7 8
    '''
    r_ = r // 3
    c_ = c // 3
    box_num = 3*r_+c_
    tmp = [0,1,2]
    
    for r__ in list(map(lambda x: 3*r_ + x, tmp)):
        for c__ in list(map(lambda x: 3*c_ + x, tmp)):
            if sudoku[r__][c__] != 0:
                remove_candidate.add(sudoku[r__][c__])
    candidate = candidate - remove_candidate
    return candidate

position_zeros = []

for r in range(9):
    for c in range(9):
        if sudoku[r][c] == 0:
            position_zeros.append((r,c))

if __debug__:
    pass
else:
    print(f'position_zeros : {position_zeros}')

def dfs(sudoku, position_zeros_index):
    if __debug__:
        pass
    else:
        print("#################################################")
        print(f'function arguments : {sudoku, position_zeros_index}')
    if position_zeros_index == len(position_zeros):
        return True

    r, c = position_zeros[position_zeros_index]

    candidate = list(find_candidate(sudoku, r, c))

    if len(candidate) == 0:
        return False

    candidate.sort()
    if __debug__:
        pass
    else:
        print(f'current sudoku : {sudoku}')
        print(f'current candidate : {candidate}')

    for can in candidate:
        sudoku[r][c] = can
        ret = dfs(sudoku, position_zeros_index + 1)

        if not ret:
            sudoku[r][c] = 0
            continue
        else:
            return True
    return False

dfs(sudoku, 0)
for i in range(9):
    print(''.join(list(map(str, sudoku[i]))))

 

매번 candidate에 대해 가로 9칸, 세로 9칸, 박스 9칸 전부를 조사하는 것이 아니라 memory array를 만들어 기억을 하면 좀더 빠르게 처리를 할 수 있습니다. 

 

실제 구현은 아래와 같습니다.

import sys


sudoku = [list(map(int,list(sys.stdin.readline().rstrip()))) for _ in range(9)]
row_memory = [[False] * 10 for _ in range(9)]
col_memory = [[False] * 10 for _ in range(9)]
box_memory = [[False] * 10 for _ in range(9)]

# build memory
for i in range(9):
    for j in range(9):
        value = sudoku[i][j]
        row_memory[i][value] = True
        col_memory[j][value] = True
        # which box? 
        '''
        0 1 2
        3 4 5
        6 7 8
        '''
        r = i // 3
        c = j // 3
        box_num = 3*r+c
        box_memory[box_num][value] = True

def find_candidate(r, c):
    r_ = r // 3
    c_ = c // 3
    box_num = 3*r_+c_
    candidate = []
    for i in range(1,10):
        if row_memory[r][i] == False and col_memory[c][i] == False and box_memory[box_num][i] == False:
            candidate.append(i)
    return candidate

position_zeros = []

for r in range(9):
    for c in range(9):
        if sudoku[r][c] == 0:
            position_zeros.append((r,c))

if __debug__:
    pass
else:
    print(f'position_zeros : {position_zeros}')

def dfs(sudoku, position_zeros_index):
    if __debug__:
        pass
    else:
        print("#################################################")
        print(f'function arguments : {sudoku, position_zeros_index}')
    if position_zeros_index == len(position_zeros):
        return True

    r, c = position_zeros[position_zeros_index]

    candidate = find_candidate(r,c)

    if len(candidate) == 0:
        return False

    candidate.sort()
    if __debug__:
        pass
    else:
        print(f'current sudoku : {sudoku}')
        print(f'current candidate : {candidate}')

    for can in candidate:
        sudoku[r][c] = can

        # modify memory
        row_memory[r][can] = True
        col_memory[c][can] = True
        r_ = r // 3
        c_ = c // 3
        box_num = 3*r_+c_
        box_memory[box_num][can] = True

        ret = dfs(sudoku, position_zeros_index + 1)

        if not ret:
            sudoku[r][c] = 0
            # modify memory
            row_memory[r][can] = False
            col_memory[c][can] = False
            box_memory[box_num][can] = False
            continue
        else:
            return True
    
    return False

dfs(sudoku, 0)
for i in range(9):
    print(''.join(list(map(str, sudoku[i]))))