[백준/c++] 18290번: NM과 K(1)

 

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

18290번: NM과 K (1)

 

 

이 문제는 BackTracking인데, BFS/DFS의 dx, dy 유형을 가미한 것 같다.

BT에서 k개를 선택했으면 ans를 max value로 갱신하고 나가는 기저 조건은 동일한데, 여기서 인접 칸은 선택하면 안 되는 게 관건이다.

이를 위해서, 칸을 선택하기 전에 이 칸의 인접한 칸이 선택되어있는지 체크해줘야 한다.

인접칸이 선택되어있다면 이 칸은 선택하면 안 되기 때문! 

 

선택하지 않은 칸을 선택하고, 그 칸의 인접칸을 찾고 만약 지금까지 선택한 칸이 있다면(visit배열 값이 true일 것)

이 칸은 선택하면 안된다. 그러므로 flag 깃발을 꽂아서 이 칸을 선택하지 못하게 한다.

 

인접 칸들을 모두 보고 나서 만약 flag가 true라면 선택된 인접 칸이 없다는 뜻이므로 선택하고 BT로 들어가서 이어간다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, k, arr[11][11], ans = -2147483648;
bool visit[11][11];
int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

void BT(int cnt, int sum){
    if(cnt == k){ //k개 선택 완료
        ans = max(ans, sum);
        return;
    }
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(!visit[i][j]){
                bool flag = true;
                for(int k=0; k<4; k++){
                    int dx = i + dir[k][0];
                    int dy = j + dir[k][1];
                    if(0<=dx&&dx<n&&0<=dy&&dy<m) if(visit[dx][dy]) flag = false;
                }
                if(flag){
                    visit[i][j] = true;
                    BT(cnt+1, sum+arr[i][j]);
                    visit[i][j] = false;
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for(int i=0; i<n; i++) for(int j=0; j<m; j++) cin >> arr[i][j];
    BT(0, 0);
    cout << ans << '\n';
    return 0;
}