[SWEA, 완전 검색] 완전 검색

 

주의점으로는 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]]:
            dx, dy = x+i, y+j
            if 0<=dx<n and 0<=dy<n:
                stack.append([dx, dy, hab+arr[dx][dy]])
    print('#%d'%tc, end=' ')
    print(result)