[알고리즘/백준] 18290: NM과 K(1)(python)

2차원 백트래킹 문제이다. visited 리스트를 만들어 풀어도 되지만...
2중 for문을 이용하여 하나씩 탐색한다. 오른쪽, 아래로만 이동하게 만들어 간단하게 만들었다.
또한 넘겨주는 값에 합과 깊이를 함께 넘겨줬다.

def dfs(x, y, d, s):
    global ans
    if d == K:
        ans = max(ans, s)
        return
    else:
        for i in range(x, N):
            for j in range(y if i == x else 0, M):
                if [i, j] not in q:
                    if ([i + 1, j] not in q) and ([i - 1, j] not in q) and ([i, j + 1] not in q) and ([i, j - 1] not in q):
                        q.append([i, j])
                        dfs(i, j, d + 1, s + a[i][j])
                        q.pop()


N, M, K = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
q = []
ans = -1e10
dfs(0, 0, 0, 0)
print(ans)