글 읽기 - 17070 재귀함수 런타임 에러 시간초과

sunggil1012 2년 전 0

파이썬으로 재귀함수를 사용해서 문제를 풀었는데 런타임에러(시간 초과) 하지 않을 방법 없을까요?

dx=[0,1,1]
dy=[1,1,0]

def DFS(x,y,ch):
    global cnt
    if x==n-1 and y==n-1:
        cnt+=1
    else:
        if ch==0:
            for i in range(2):
                xx=x+dx[i]
                yy=y+dy[i]
                if i==1:
                    if 0<=xx<=n-1 and 0<=yy<=n-1 and mtx[xx-1][yy]==0 and mtx[xx][yy-1]==0 and mtx[xx][yy]==0:
                        ch=1
                        DFS(xx,yy,ch)
                elif i==0:
                    if 0<=xx<=n-1 and 0<=yy<=n-1 and mtx[xx][yy]==0:
                        ch=0
                        DFS(xx,yy,ch)
              
        elif ch==1:
            for i in range(3):
                xx=x+dx[i]
                yy=y+dy[i]
                if i==1:
                    if 0<=xx<=n-1 and 0<=yy<=n-1 and mtx[xx-1][yy]==0 and mtx[xx][yy-1]==0 and mtx[xx][yy]==0:
                        ch=1
                        DFS(xx,yy,ch)
                elif i==0:
                    if 0<=xx<=n-1 and 0<=yy<=n-1 and mtx[xx][yy]==0:
                        ch=0
                        DFS(xx,yy,ch)
                elif i==2:
                    if 0<=xx<=n-1 and 0<=yy<=n-1 and mtx[xx][yy]==0:
                        ch=2
                        DFS(xx,yy,ch)
                        
        elif ch==2:
             for i in range(1,3):
                xx=x+dx[i]
                yy=y+dy[i]
                if i==1:
                    if 0<=xx<=n-1 and 0<=yy<=n-1 and mtx[xx-1][yy]==0 and mtx[xx][yy-1]==0 and mtx[xx][yy]==0:
                        ch=1
                        DFS(xx,yy,ch)
                elif i==2:
                    if 0<=xx<=n-1 and 0<=yy<=n-1 and mtx[xx][yy]==0:
                        ch=2
                        DFS(xx,yy,ch)
          
                    
n=int(input())
mtx=[list(map(int,input().split())) for _ in range(n)]
mtx[0][0],mtx[1][0]=1,1
# ch: 가로0 대각선1 세로2
ch=0
cnt=0
DFS(0,1,0)
print(cnt)

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

문제

문제

출처

ICPC

17070 재귀함수 런타임 에러 시간초과

sunggil1012 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말