1 minute read

18290번 : NM과 K (1)

문제 링크

https://www.acmicpc.net/problem/18290

문제 설명

크기가 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. dfs를 구성하고, 선택한 칸 이전의 칸들은 선택할 필요가 없게 반복문을 구성하여 시간을 줄인다.
  2. 선택한 수 및 상하좌우 칸은 선택하지 못하게 check 배열을 따로 만들어 확인한다.
  3. 격자판에 들어가있는 수는 -10,000까지는 되므로 처음 max_value를 선언할 때 주의하여 선언한다.
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 + arr[i][j])
                check[i][j] = False


N, M, K = map(int, input().split())
arr = []
for _ in range(N) :
    arr.append(list(map(int, input().split())))

max_value = -50000
check = [[False for _ in range(M)] for _ in range(N)]
dfs(0, 0, 0, 0)
print(max_value)

Comments

You May Also Enjoy