[백준] 18290번 NM과 K (1) 파이썬

문제

크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. r행 c열에 있는 칸을 (r, c)라고 했을 때, (r-1, c), (r+1, c), (r, c-1), (r, c+1)에 있는 칸이 인접한 칸이다.

입력

첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에 격자판에 들어있는 수가 주어진다.

출력

선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 출력한다.

제한

• 1 ≤ N, M ≤ 10
• 1 ≤ K ≤ min(4, N×M)
• 격자판에 들어있는 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.
• 항상 K개의 칸을 선택할 수 있는 경우만 입력으로 주어진다.

예제 입력 1

1 1 1
1

예제 출력 1

1

참고 답안

import sys

input = sys.stdin.readline

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

n, m, k = map(int, input().split())
answer = -sys.maxsize
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]


def dfs(y, x, cnt, _sum):
    global answer
    if cnt == k:
        answer = max(answer, _sum)
        return
    for i in range(y, n):
        for j in range(x if i == y else 0, m):
            if visited[i][j]:
                continue
            for z in range(4):
                ny = i + dy[z]
                nx = j + dx[z]
                if 0 <= ny < n and 0 <= nx < m and visited[ny][nx]:
                    break
            else:
                visited[i][j] = True
                dfs(i, j, cnt + 1, _sum + graph[i][j])
                visited[i][j] = False


dfs(0, 0, 0, 0)
print(answer)