인프런 커뮤니티 질문&답변

꼬모님의 프로필 이미지

작성한 질문수

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

섹션 7 10번 미로탐색 반복 깊이 초과 에러

23.05.25 21:41 작성

·

169

·

수정됨

0

#my sol 
def DFS(x,y):
    global cnt
    if x>7 or y>7:
        return
    if x==7 and y==7:
        cnt+=1
    else:
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if maze[nx][ny]==0:
                maze[nx][nx]=1
                DFS(nx,ny)
                maze[nx][nx]=0
    

if __name__=='__main__':
    maze = [list(map(int, input().split())) for _ in range(7)]
    maze.insert(0,[1]*7)
    maze.append([1]*7)
    for row in maze:
        row.insert(0,1)
        row.append(1)
    cnt=0
    dx=[-1,0,1,0]
    dy=[0,1,0,-1]
    maze[1][1]=1
    DFS(1,1)
    print(cnt)

#solution
dx=[-1,0,1,0]
dy=[0,1,0,-1]
def DFS(x,y):
    global cnt
    if x==6 and y==6:
        cnt+=1
    else:
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<=6 and 0<=ny<=6 and maze[nx][ny]==0:
                maze[nx][nx]=1
                DFS(nx,ny)
                maze[nx][nx]=0
    

if __name__=='__main__':
    maze = [list(map(int, input().split())) for _ in range(7)]
    cnt=0
    maze[0][0]=1
    DFS(0,0)
    print(cnt)

위의 코드는 강의 듣기 전에 혼자 작성한 코드이고, 아래는 강의에서 알려주신 코드입니다. 두 코드가 접근 방식이 같은 것은 알고 있습니다. 그런데 제 컴퓨터에서 두 코드 모두 채점 프로그램을 돌렸을 때 결과 계산을 하지 못 합니다.(5초짜리로 해도 같고, 코드에 setrecursionlimit 추가해도 같음)

import sys
sys.setrecursionlimit(10**6)

그리고 pdf 예제조차도 RecursionError: maximum recursion depth exceeded in comparison 에러가 납니다.(예제는 setrecursionlimit 추가 시 파이썬이 응답을 멈춰서 강제 종료됨) 혹시 제가 발견하지 못 한 코드 상의 문제가 있는 것인지、 제 컴퓨터 사양 때문인지 궁금합니다。

답변 1

0

김태원님의 프로필 이미지
김태원
지식공유자

2023. 05. 27. 15:08

안녕하세요^^

오타입니다.

maze[nx][nx]=1
꼬모님의 프로필 이미지
꼬모
질문자

2023. 05. 27. 16:28

감사합니다 로직이 틀렸을 거라 생각했지 설마 인덱스를 틀릴 거라 생각을 못 해 제대로 안 봤나봐요

꼬모님의 프로필 이미지

작성한 질문수

질문하기