알고리즘 문제풀이 [백준 18290]

🔎 BACKJOON 18290

• 문제

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

• 입력

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

• 출력

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

#include <iostream>
#define MAX 10
using namespace std;

int n, m, k;
int ans = -210000000;
int n_arr[MAX][MAX] = {0};
bool visited[MAX][MAX] = {0};
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

void dfs(int cnt, int sum){
    if (cnt == k) {
        if (ans < sum) ans = sum;
        return;
    }
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            if(visited[i][j])
                continue;
            bool ok = true;
            for (int z = 0; z < 4; z++){
                int nx = i + dx[z];
                int ny = j + dy[z];
                if((nx >= 0 && nx < n) && (ny >= 0 && ny < m)){
                    if(visited[nx][ny]){
                        ok = false;
                    }
                }
            }
            if(ok){
                visited[i][j] = true;
                dfs(cnt + 1, sum + n_arr[i][j]);
                visited[i][j] = false;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            cin >> n_arr[i][j];
        }
    }
    dfs(0, 0);

    cout << ans;
}

앞서 배운 n과 m을 이해하고 dfs와 백트래킹을 사용하여 푸는 문제.

문제 링크

풀이 깃허브 링크