[Python - 백준 18290] NM과 K(1)

18290번: NM과 K (1)

문제 설명

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

제한 사항

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

입력형식

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

 

출력형식

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

입출력 예시

풀이 과정

백트래킹을 이용하여 풀 수 있는 문제였다. 처음에 문제를 풀떄 최대값을 구하는 걸 보고 bfs로 풀 수 있을거 같아서 bfs로 접근했지만, 2*2 배열은 결과가 잘 나왔지만 3개를 고르는 문제부터 정답에 근접할 수 없었다. 그래서 dfs로 다시 접근해서 풀 수 있었다. x,y를 모두 조합해야되는 문제라서 복잡했다. 하지만 2차원 for문을 이용하여 풀고, 상하좌우 중 아래,오른쪽으로만 이동할 수 있게 하여 복잡성을 줄였고, 선택된 i,j 의 값에 상하좌우가 모두 False여야 되므로 상하좌우를 이동할 수 있는 dxy 를 만들어 nx,ny의 값이 모두 False일 때만 다음 dfs를 실행하도록 구현했다.

 

def dfs(x, y, cnt, sum_value):
    dxy = [(-1, 0), (1, 0), (0, 1), (0, -1)]
    if cnt == k:
        global max_value
        max_value = max(max_value, sum_value)
        return
    for i in range(x, n):
        for j in range(y if i == x else 0, m):
            if check[i][j]:
                continue
            for dx, dy in dxy:
                nx, ny = i + dx, j + dy
                if 0 <= nx < n and 0 <= ny < m and check[nx][ny]:
                    break
            else:
                check[i][j] = True
                dfs(i, j, cnt + 1, sum_value + item[i][j])
                check[i][j] = False


if __name__ == '__main__':
    n, m, k = map(int, input().split())
    item = []
    for _ in range(n):
        item.append(list(map(int, input().split())))

    max_value = 0
    check = [[False for _ in range(m)] for _ in range(n)]
    dfs(0, 0, 0, 0)
    print(max_value)