글 읽기 - 재귀함수 반복문 속도차이 질문드려요(정답 스포주의)

alsrjs0725 2년 전 0

재귀함수로 알고리즘을 작성 후 문제를 풀었는데 시간과 메모리가 너무 많이 사용되어 알고리즘을 최적화 해보자 재귀함수를 반복문으로 바꿔보았습니다

재귀함수 대신 스택에 스도쿠 판을 추가하여 반복될때마다 이를 마지막에 추가된것부터 빼서 검색 하도록 바꿨습니다

그러고 제출해보니 재귀함수는 3300ms인것에 비해 반복문은 4200ms가 나오더군요(메모리 사용량은 확실히 줄었습니다)

제가 알기로는 재귀함수는 모듈을 호출하면서 시간이 걸려 반복문이 더 빠른것으로 알고있는데 왜 저는 반복문이 아닌 재귀함수가 더 빠른걸까요?

#재귀함수
import sys
sudoku = []
for i in range(9):#초기 스도쿠 판을 sudoku에 2차원 리스트로 저장
    sudoku.append(list(map(int,input().split())))
def solve(board:list):
    for i in range(9):
        try:
            a = board[i].index(0)#스도쿠 판중 0을 찾기
        except:
            if i == 8: #마지막줄까지 0이 없다면 스도쿠 판을 출력 후 프로그램 종료
                print('\n'.join(list(map(lambda x:' '.join(list(map(str,x))),board))))
                sys.exit()
        else:
            b = board[(i//3)*3][(a//3)*3:(a//3)*3+3]+board[((i//3)*3+1)][(a//3)*3:(a//3)*3+3]+board[(i//3)*3+2][(a//3)*3:(a//3)*3+3]#빈공간이 속해있는 3*3칸의 내용물을 리스트로 추출
            for j in range(1,10):
                if not(j in board[i] or j in list(map(lambda x:x[a],board)) or j in b):#가로,세로,3*3칸에 j가 없다면
                    board[i][a] = j#0이 적혀있는 칸을 조건의 맞는 숫자로 변경
                    c = list(map(lambda x:x[:],board))
                    solve(c)#얕은복사를 주의하며 solve를 호출
            break
solve(list(map(lambda x:x[:],sudoku)))#얕은복사를 주의하며 solve를 호출

#반복문
import sys
stack = []
sudoku = []
for i in range(9):
    sudoku.append(list(map(int,input().split())))
stack.append(sudoku)
while True:
    board = list(map(lambda x:x[:],stack.pop()))
    for i in range(9):
        try:
            a = board[i].index(0)
        except:
            if i == 8:
                print('\n'.join(list(map(lambda x:' '.join(list(map(str,x))),board))))
                sys.exit()
        else:
            b = board[(i//3)*3][(a//3)*3:(a//3)*3+3]+board[((i//3)*3+1)][(a//3)*3:(a//3)*3+3]+board[(i//3)*3+2][(a//3)*3:(a//3)*3+3]
            for j in range(9,0,-1):
                if not(j in board[i] or j in list(map(lambda x:x[a],board)) or j in b):
                    board[i][a] = j
                    c = list(map(lambda x:x[:],board))
                    stack.append(c)
            break

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

문제

문제

출처

ICPC

재귀함수 반복문 속도차이 질문드려요(정답 스포주의)

alsrjs0725 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말