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

18290번: NM과 K (1)

---

백트래킹

---

---

• 제목

NM과 K(1)

---

• 조건

시간 제한 : 2 초

메모리 제한 : 512 MB 

---

• 문제

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

---

• 입력

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

---

• 출력

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

---

예제 입력1	예제 출력1
1 1 1 1	1

예제 입력2	예제 출력2
2 2 2 1 2 3 4	5

예제 입력3	예제 출력3
2 2 2 5 4 4 5	10

예제 입력4	예제 출력4
5 5 3 1 9 8 -2 0 -1 9 8 -3 0 -5 1 9 -1 0 0 0 0 9 8 9 9 9 0 0	27

---

dx = [0, -1]
dy = [-1, 0]
MAXIMUM = -9876543210
def NMK(curr, sum):
    global MAXIMUM
    cx = curr // M
    cy = curr % M
    # 미추가
    if curr + 1 < N * M:
        NMK(curr + 1, sum)
    # 추가
    for k in range(2):
        nx = cx + dx[k]
        ny = cy + dy[k]
        if nx < 0 or ny < 0 or nx >= N or ny >= M:
            continue
        next = nx * M + ny
        if next in used:
            return
    used.add(curr)
    sum += arr[cx][cy]
    if len(used) == K:
        MAXIMUM = max(MAXIMUM, sum)
    else:
        if curr + 1 < N * M:
            NMK(curr + 1, sum)
    used.remove(curr)
N, M, K = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))
used = set()
NMK(0, 0)
print(MAXIMUM)