[Baekjoon/C++] 18290번 - NM과 K (1)

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

 

---

풀이

#include <iostream>
using namespace std;

void dfs(int dth, int num, int start);

int N, M, K;
int big = -100000000;

int arr[11][11];
bool check[11][11] = { false };

void dfs(int dth, int num, int start) {
    if (dth == K) {
        big = max(big, num);
        return;
    }

    for (int i = start; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (check[i][j] || check[i - 1][j] || check[i + 1][j] || check[i][j - 1] || check[i][j + 1]) continue;

            check[i][j] = true;
            dfs(dth + 1, num + arr[i][j], i);
            check[i][j] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++) cin >> arr[i][j];

    dfs(0, 0, 1);

    cout << big << '\n';

    return 0;
}

 

void dfs(int dth, int num, int start) {
    if (dth == K) {
        big = max(big, num);
        return;
    }

    for (int i = start; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (check[i][j] || check[i - 1][j] || check[i + 1][j] || check[i][j - 1] || check[i][j + 1]) continue;

            check[i][j] = true;
            dfs(dth + 1, num + arr[i][j], i);
            check[i][j] = false;
        }
    }
}

크기가 N * M인 배열에서 서로 인접하지 않는 K개의 숫자를 선택해 최댓값을 구하는 함수이다. 선택한 숫자의 상하좌우를 확인해야 하므로 배열을 [11][11] 사이즈로 넉넉하게 선언해서 배열을 범위를 넘지 않도록 했다. 상하좌우를 확인할 때 for문을 사용하는 방법도 있으나 최대한 시간을 단축하고 싶었고, 확인하는 경우도 그렇게 많지 않았기에 if문 하나에 모든 조건을 넣는 방식으로 코드를 짰다.