[Baekjoon] 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개의 칸을 선택할 수 있는 경우만 입력으로 주어진다.

예제

Example 1:

Input: 
1 1 1
1
Output: 
1

Example 2:

Input:
2 2 2
1 2
3 4
Output:
5

Example 3:

Input:
2 2 2
5 4
4 5
Output:
10

Example 4:

Input:
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
Output:
27

조건

시간 제한 : 2초

메모리 제한 : 512 MB

풀이과정

풀이 1

재귀를 이용한 브루트포스 방식으로 해결하였다.

n, m, k = map(int, input().split())

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

check = [[False]*m for _ in range(n)]
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
ans = -int(1e9)
def dfs(level, res):
    global ans
    if level == k:
        ans = max(ans, res)
        return
    else:
        for i in range(n):
            for j in range(m):
                if check[i][j]:
                    continue
                ch = False
                for p in range(4):
                    nx = i + dx[p]
                    ny = j + dy[p]
                    if 0 <= nx < n and 0 <= ny < m and check[nx][ny] == True:
                        ch = True
                        break
                if not ch:
                    check[i][j] = True
                    dfs(level+1, res+arr[i][j])
                    check[i][j] = False

dfs(0, 0)
print(ans)

풀이 2

하지만 풀이 1의 경우 중복으로 확인하는 문제가 있다. 따라서 이 중복을 없애야 한다. 따라서 재귀 호출시 방문한 지점을 고려하여 그 이후의 지점만 확인할 수 있도록 한다.

import sys

input = sys.stdin.readline

n, m, k = map(int, input().split())

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

check = [[False]*m for _ in range(n)]


ans = -int(1e9)


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


def dfs(level, csum, a, b):

    global ans
    if level == k:
        ans = max(ans, csum)
        return
    else:
        for i in range(a, n):
            for j in range(b if i == a else 0,m):
                if check[i][j]:
                    continue
                ch = False
                for p in range(4):
                    nx = i + dx[p]
                    ny = j + dy[p]
                    if 0 <= nx < n and 0 <= ny < m and check[nx][ny] == True:
                        ch = True
                        break
                if not ch:
                    check[i][j] = True
                    dfs(level+1, csum+arr[i][j], i, j)
                    check[i][j] = False
dfs(0, 0, 0, 0)
print(ans)