Python - 경주로 건설 (DFS, 메모이제이션)

https://school.programmers.co.kr/learn/courses/30/lessons/67259

프로그래머스

 
1. 다음 지점이 기록되어있지 않다면 비용으로 기록 후 탐색합니다.
2. 기록되어 있다면 기록된 비용과 현재 비용을 비교하여 현재 비용이 더 낮다면 다시 탐색합니다.
 
애매한 코드
 - 프로그래머스 테스트케이스가 25개 밖에 없기 때문에 통과할 수 있었던 것 같습니다. 만약 더욱 다양한 테스트 케이스가 있었다면 통과하지 못했을 겁니다. 

 - dire배열을 상하좌우 순으로 배치하면 테스트 케이스 14번 25번이 실패합니다.
     * 우상하좌 순으로 배치하면 통과합니다.
2) 중간에서 만나는 지점(예제 좌표 [3, 4])에서 비용이 무조건 작은 경우에만 탐색할 경우 제가 작성한 코드는 방향 순서에 따라 답이 달라집니다.
2_1) 예제

[[0, 0, 0, 0, 0, 0, 0, 0],
 [1, 0, 1, 1, 1, 1, 1, 0],
 [1, 0, 0, 1, 0, 0, 0, 0],
 [1, 1, 0, 0, 0, 1, 1, 1],
 [1, 1, 1, 1, 0, 0, 0, 0],
 [1, 1, 1, 1, 1, 1, 1, 0],
 [1, 1, 1, 1, 1, 1, 1, 0],
 [1, 1, 1, 1, 1, 1, 1, 0]]
 # answer = 4500

(상하좌우 -> 4900, 우상하좌 -> 4500)
참고 https://school.programmers.co.kr/questions/42984

프로그래머스

import sys
sys.setrecursionlimit(1000)

def solution(board):
    def DFS(x, y, before): # 좌표, before : 탐색했던 방향
        for d in range(4):
            c = board[x][y] + 100 if before == (d + 1) or before == 0 else board[x][y] + 600
            # 시작점으로 돌아가지 않기
            if x + dire[0][d] == 0 and y + dire[1][d] == 0: continue
            if x + dire[0][d] < 0 or x + dire[0][d] >= len(board[0]): continue
            if y + dire[1][d] < 0 or y + dire[1][d] >= len(board[0]): continue
            if board[x + dire[0][d]][y + dire[1][d]] == 1 : continue
            
            # 기록 되었던 곳보다 비용이 높으면 continue
            if board[x + dire[0][d]][y + dire[1][d]] != 0 and board[x + dire[0][d]][y + dire[1][d]] < c: continue
            
            board[x + dire[0][d]][y + dire[1][d]] = c
            DFS(x + dire[0][d], y + dire[1][d], (d + 1))
        
    #dire = [[-1, 1, 0, 0], [0, 0, -1, 1]]
    
    # 우 하 상 좌
    dire = [[0, 1, -1, 0], [1, 0, 0, -1]]
    DFS(0, 0, 0)
    return board[len(board) - 1][len(board) - 1]