나만의 개발블로그

흠... 너무 오래걸렸다.. 오래 걸린 이유는 아래와 같은 tc의 경우에 [0,1]인 18부터 시작할 경우 우선 48,55 이렇게 두 가지 경로로 갈 수가 있는데 48로 가는 순간 다시 0번째 행으로 가게 되어서 34를 조회하게 되는 경우가 발생하게 되는 것 때문에 너무 오래 걸렸다... 0 18 34 48 0 55 18 7 0 그래서 1로 가지 않게 for문을 1, n으로 두고 마지막에 cnt 가 n-2의 경우에 s행의 0번째 인덱스 값을 더해줘 해결하도록 했음. def search(s, hap, cnt): global mx_hap if cnt == n-2: mx_hap = min(mx_hap, hap+arr[s][0]) return if hap >= mx_hap: return for i in rang..

주의점으로는 elif 문을 추가해 hab이 현재 result 값 보다 큰 값일 경우엔 더 이상 조사하지 않도록 해주기! for tc in range(1, int(input())+1): n = int(input()) arr = [list(map(int,input().split())) for _ in range(n)] result = 11*n*n # dfs 사용 stack = [[0, 0, arr[0][0]]] while stack: x,y,hab = stack.pop() if x == n-1 and y == n-1: if result > hab: result = hab continue elif hab >= result: continue # 오른쪽, 아래만 탐색 for i,j in [[0, 1], [1, 0..