2580

날짜 : 2023. 6. 22

사용 언어 : python

 

문제

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

 

 

코드

import sys
# sys.setrecursionlimit(10**9)

# 행 체크
def check_row(val, c):
    for i in range(9):
        if val == graph[i][c]:
            return False
    return True

# 열 체크
def check_col(r, val):
    for i in range(9):
        if val == graph[r][i]:
            return False
    return True

# 박스 체크
def check_box(r, c, val):
    a = int(r // 3) * 3
    b = int(c // 3) * 3
    for i in range(a, a + 3):
        for j in range(b, b + 3):
            if val == graph[i][j]:
                return False
    return True


def backtracking(idx):
    # print(idx)
    if idx == len(check):
        for row in graph:  # 수도쿠 완성
            print(*row)
        exit(0)

    r, c = check[idx][0], check[idx][1]
    for i in range(1, 10):
        if check_row(i, c) and check_col(r, i) and check_box(r, c, i):  # 이미 있는 값 체크
            graph[r][c] = i # 설정
            backtracking(idx + 1)
            graph[r][c] = 0  # 리턴

graph = list()
for _ in range(9):
    graph.append(list(map(int, sys.stdin.readline().split())))  # 조건에 맞게 입력
check = list()

for i in range(9):
    for j in range(9):
        if graph[i][j] == 0:
            check.append((i, j))  # 빈칸 위치 체크
# print(check)
backtracking(0)

 

 

풀이

- 시중의 수도쿠를 푸는 방식으로 풀이한다.

- 조건에 따라 입력받고, 0(공백)의 인덱스를 저장하는 리스트를 따로 만들어 저장한다.

- 그 다음, 해당 인덱스를 기준으로 백트래킹을 수행한다.

- 1부터 9까지 루프를 돌리면서, 행, 열, 박스 단위로 삽입 가능한지 체크한 후 가능한 경우에 값을 넣고 다음 공백의 위치로 재귀한다.

- 이후에 계속 재귀한 후, 공백을 갖고 있는 리스트의 인덱스를 오버한 경우(전부 채운 경우) 값을 출력한 후 프로그램을 종료한다.

 

 

알게된 점

- 풀이는 금방 할 수 있었지만 파이썬 특유의 느린것 때문에 시간초과와 싸웠다.

- 분명 풀이는 확실한데 왜 시간초과가 발생하는지;;

- 찾아보니까 대부분 pypy3로 풀이를 제출했고, 시간초과를 회피하고자 pypy3로 제출했는데 또 메모리초과가 발생했다.

- 그래서 찾아보니까 python에서 sys.setrecursionlimit()은 메모리를 괄호 안의 수에 따라 미리 할당하기 때문에 재귀에서 메모리 초과가 쉽게 발생할 수 있다는 글을 보았다.

- 그래서 sys.setrecursionlimit()를 주석처리 한 후 돌리니까 바로 풀림....

 

 

참고 사이트

-