2239 스도쿠

고오급 알고리즘 스터디 - 4

풀이

1번째 시도 : O(N^N^2)

• 모든 부분에 대해 숫자를 대입하게 된다면 O(N^N^2) 으로 N이 작더라도 시간초과가 발생하게 된다.
• O(N^N^2) 의 경우 N이 4 이상이 된다면 100,000,000 을 넘는 값을 갖게 된다.

2번째 시도

조건
1. 같은 열에 속한 숫자들은 중복을 허용하지 않는다.
2. 같은 행에 속한 숫자들은 중복을 허용하지 않는다.
3. 같은 구역에 속한 숫자들은 중복을 허용하지 않는다.

+ 4. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다.

백트래킹
- 모든 값을 해결하면 True
- 1 ~ 9 까지 값을 돌며 진행
- 행, 열, 구역에 중복 값이 없다면 해당 부분 설정
- 다음 구역을 대상으로 함수 진행
- 끝까지 도달하지 못한 경우 해당 값이 설정되기 전으로 복귀

• a in list : O(N) VS a in set : O(1)

import sys
numbers = {1: '1', 2: '2', 3: '3', 4: '4', 5: '5', 6: '6', 7: '7', 8: '8', 9: '9'}


def backtracking(index, size):
    if index == size:
        return True

    x, y = need_to_write[index]
    number = 1
    space_index = x//3*3 + y//3

    while number <= 9:
        if numbers[number] in set_row[x] or numbers[number] in set_col[y] or numbers[number] in set_space[space_index]:
            number += 1
            continue

        set_row[x].add(numbers[number])
        set_col[y].add(numbers[number])
        set_space[space_index].add(numbers[number])
        graph[x][y] = numbers[number]

        if backtracking(index+1, size):
            return True
        set_row[x].remove(numbers[number])
        set_col[y].remove(numbers[number])
        set_space[space_index].remove(numbers[number])

        number += 1

    return False


need_to_write = []
set_row = [set() for _ in range(9)]
set_col = [set() for _ in range(9)]
set_space = [set() for _ in range(9)]
graph = [list(sys.stdin.readline().rstrip()) for _ in range(9)]

for x in range(9):
    for y in range(9):
        if graph[x][y] == '0':
            need_to_write.append((x, y))
        else:
            set_row[x].add(graph[x][y])
            set_col[y].add(graph[x][y])
            set_space[x//3*3 + y//3].add(graph[x][y])

size = len(need_to_write)
backtracking(0, size)

for g in graph:
    sys.stdout.write(''.join(g) + '\n')

2239 스도쿠