[BOJ/Silver 1] 백준 18290 NM과 K (1)(C++)

문제 링크

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

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

 

예제 입력 1

1 1 1
1

예제 출력 1

1

예제 입력 2

2 2 2
1 2
3 4

예제 출력 2

5

예제 입력 3

2 2 2
5 4
4 5

예제 출력 3

10

예제 입력 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

예제 출력 4

27

 

알고리즘 분류

• 백트래킹

 

풀이

칸 하나를 선택했으면 인접한 칸까지 선택된 것으로 처리한다.

선택이 되었는지 안 되었는지가 아닌 선택된 횟수를 기록하고, 선택된 횟수가 0회인 칸만을 선택한다.

합의 최댓값이 음수가 될 수도 있다는 것에 주의한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 11
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M, K;
int MAP[MAX][MAX], Visited[MAX][MAX];
int Answer = -INF;

void input() {
    cin >> N >> M >> K;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> MAP[i][j];
        }
    }
}

void dfs(int Depth, int Sum) {
    if (Depth == K) {
        Answer = max(Answer, Sum);
        return;
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (Visited[i][j] == 0) {
                Visited[i][j]++;
                Visited[i + 1][j]++;
                Visited[i][j + 1]++;
                Visited[i - 1][j]++;
                Visited[i][j - 1]++;
                dfs(Depth + 1, Sum + MAP[i][j]);
                Visited[i][j - 1]--;
                Visited[i - 1][j]--;
                Visited[i][j + 1]--;
                Visited[i + 1][j]--;
                Visited[i][j]--;
            }
        }
    }
}

void settings() {
    dfs(0, 0);
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}