swe 2117 홈 방벙 서비스

- bfs - 한번 홀수 짝수 구분을 명확히 해야 합니다. - 명확하게 k 에 대해서 정해주도록 합니다.

/*
2221 홈방법서비스
제공받는 집들은 각각 M의 비용 지불,
최대한 많은 집에 홈방법 서비스를 제공

K는 1이상의 정수입니다.
K를 늘려가면서 검사를 진행하도록 합니다.
K는 얼마까지 커질 수 있는지? K의 가장 큰 값은
K가 3일때 3*3까지 커버가 가능합니다.
맵이 3*3 이면 K는 3*3 까지 검사하도록 합니다.

1. k 를 1부터 K까지 선정하고, // 맵을 넘어가는 경우 예외처리 주의.
2. 2중 포문을 돌려서 그 안의 집의 숫자를 계산합니다.
3. 회사가 이익이 나는지 확인을 하도록 합니다.

회사가 이익이 남는 케이스 중에서 집의 수자가 가장 많은 집의 수를 출력합니다.
*/
 
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define SIZE 25
int map[SIZE][SIZE];
int N, M;
int maxVal;
struct point {
    int x, y;
};
queue<point> que;
int visit[SIZE][SIZE];
int x, y, nx, ny;
int cost;
int home_cnt;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int repeat_cnt;
int total_home_cnt;
 
void problemIn() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
            if (map[i][j] == 1) {
                total_home_cnt++;
            }
        }
    }
}
 
void init() {
    maxVal = 0;
    total_home_cnt = 0;
    repeat_cnt = 0;
    cost = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            map[i][j] = 0;
        }
    }
}
 
void visit_init() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            visit[i][j] = 0;
        }
    }
}
 
void bfs(int k) {
 
    home_cnt = 0;
    repeat_cnt = 0;
    if (map[que.front().x][que.front().y] == 1) home_cnt++;
    while (!que.empty()) {
 
        if (repeat_cnt == (k - 1)) {
            while (!que.empty()) que.pop();
            return;
        }
 
        int qlen = que.size();
        while (qlen--) {
            x = que.front().x;
            y = que.front().y;
            que.pop();
 
            for (int i = 0; i < 4; i++) {
                nx = x + dx[i];
                ny = y + dy[i];
                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if (visit[nx][ny] == 0) {
                    if (map[nx][ny] == 1) home_cnt++;
                    visit[nx][ny] = 1;
                    que.push({ nx,ny });
                }
            }
        }
        repeat_cnt++;
    }
}
 
/*
k 에 대해서 가지치기를 해보도록 합니다.
K = 2 일떄 운용비용은 5 입니다.
커버 하는 지역은 5군데 입니다.
K = 3 운영비용 13 입니다.
커버 하는 지역 13입니다.

처음에 집의 개수를 구하고, 그것을 비용을 커버할 수 있는 K 까지만 하면 되겠습니다.

예를 들어서 3*3 맵에서 집이 1개이고 지불비용이 5입니다. 그럼
케이는 케이는 5까지만 가능합니다.
최대지불비용과 케이의 운영비용을 비교합니다.

*/
void solve() {
 
    //total_home_cnt * M;
 
 
 
    for (int k = 1; k <= N+1; k++) {
        cost = k*k + (k - 1)*(k - 1);
        if (total_home_cnt * M >= cost) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    visit[i][j] = 1;
                    que.push({ i,j });
                    bfs(k);
                    if ((home_cnt * M) - cost >= 0) {
                        maxVal = max(maxVal, home_cnt);
                    }
                    visit_init();
                }
            }
        }
    }
}
 
int main() {
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        problemIn();
        solve();
        cout << "#" << tc << " " << maxVal << endl;
        init();
    }
    return 0;
}