글 읽기 - [python] 2580 스도쿠

wlsgh7608 3년 전 0

python 시간초과 관련 질문드립니다.
pypy3에서 실행시 93%에서 시간초과가 발생합니다.

어디에 문제가 있을까요?

import sys
def solve(sudoku):

    n_list=set(range(1,10))

    for i in range(9):
        for j in range(9):
            if sudoku[i][j] != 0:
                continue
            row = sudoku[i]
            col = [row[j] for row in sudoku]

            divx = i // 3
            divy = j // 3
            room = []
            for p in range(divx * 3, (divx + 1) * 3):
                for q in range(divy * 3, (divy + 1) * 3):
                    room.append(sudoku[p][q])

            row_remain = n_list- set(row)
            col_remain = n_list - set(col)
            room_remain = n_list -set(room)

            #가능한 숫자
            v_list =  list(row_remain & col_remain & room_remain)

           

            for r in range(len(v_list)):
                v=v_list[r]
                if list_check(row, v) and list_check(col, v) and list_check(room, v):
                    tmp = list(sudoku)
                    tmp[i][j]=v
                    if solve(tmp):
                        sudoku =tmp

                    #v가 마지막 v_list인덱스일때
                    elif r==len(v_list)-1:
                        sudoku[i][j]=0
                        return False

            if len(v_list) == 0:
                return False
    return True
def list_check(list,v):
    if v in list:
        return False
    return True


sudoku = []
for _ in range(9):
    line = list(map(int,sys.stdin.readline().split()))
    sudoku.append(line)

solve(sudoku)


for i in sudoku:
    for j in i:
        print(j, end=" ")
    print()

cclang 3년 전 1

일단 함수가 호출될때마다 첫 이중 for문을 도는 과정에서 필요없는 과정이 반복되고 있습니다.

함수 매개변수로 x,y를 넘겨줌으로써 이미 0이아니라고 판단된 부분을 다시 검사하는 과정을 없앨 수 있습니다.

그리고 31번째 줄을 통해 또 체크를 하는 과정이 꼭 있어야되는지 생각해보는게 좋을 것 같네요.

set 1~9에서 3*3, row, col 집합을 빼준 그 set이 사용할 수 있는 수의 집합 아닌가요?

wlsgh7608 3년 전 0

댓글 감사합니다.

스도쿠를 풀었음에도 불구하고 for문이 실행되는 게 문제였습니다.

DFS을 이용하여 해결하였습니다. 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[python] 2580 스도쿠 - 시간초과 질문

wlsgh7608 3년 전 0

cclang 3년 전 1

wlsgh7608 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말