[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)에 있는 칸이 인접한 칸이다.

입력

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

출력

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

제한

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

코드

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

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

ans = -int(1e6)


def bt(lst, lst_sum, idx):
    global ans
    # k개만큼 뽑음
    if len(lst) == k:
        ans = max(ans, lst_sum)
        return
    for i in range(idx+1, n*m):
        # lst에 있는 칸들과 인접하지 않으면 재귀
        neighbor = False
        for j in lst:
            # 같은 행 인접
            if i//m == j//m and abs(i-j) == 1:
                neighbor = True
                break
            # 같은 열 인접
            if i % m == j % m and abs(i-j) == m:
                neighbor = True
                break
        if not neighbor:
            bt(lst+[i], lst_sum+board[i//m][i % m], i)


bt([], 0, -1)
print(ans)

0 이상 n*m 미만 수 중에서 k개를 뽑는 bt를 만든다. 

dfs 함수는 k개의 수를 뽑으면 뽑은 k개의 수의 합인 lst_sum과 ans를 비교하여 둘 중 큰 값을 ans에 저장하고 리턴한다.

 

그런데 k개의 수들을 뽑을 때 수가 의미하는 칸이 인접한 칸은 같이 lst에 들어갈 수 없다.

인접한 칸인지 알아내는 방법은 2가지로 나눠서 알아볼 수 있다. 

1. 같은 행에서 인접한 경우
   몇번째 행인지 알려면 수를 열의 개수인 m을 나눈 몫을 비교해봐서 같다면 같은 행인 것이다. 같은 행이라면 인접한 칸인지 알아보기 위해 둘의 차가 1인지 알아본다.
2. 같은 열에서 인접한 경우
   몇번째 열인지 알려면 수를 열의 개수인 m으로 나눈 나머지를 비교해보면 된다. 같은 열이라면 두 수의 차가 m이면 위아래로 인접한 칸이다.

이렇게 해서 다음에 살펴본 칸이 인접하지 않아서 넣을 수 있는 칸이라면 bt(lst+[i], lst_sum+board[i//m][i%m], i)를 실행해주면 된다.