2117 홈 방범 서비스

2117 홈 방범 서비스

좀 어려웠다.

처음에 서비스 영역에 해당하는 필터를 만드려고 했는데 쉽지 않았다.

그래서 bfs를 통한 탐색으로 풀었다.

1. price배열에 홈방범서비스 비용에 대한 값을 미리 계산해놓는다.

2. 각각의 지점마다 bfs 탐색을 통해 어느 범위에 몇명의 사람이 들어있는지 기록한다.

ex) d[5]=2 -> 해당지점의 5번째 범위에 2명의 사람이 있음.

3. get_result() 함수를 통해 해당 지점에서 얻을 수 있는 최대값을 구한다.

4. 모든지점에서 반복한다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <memory.h>
#define P pair<int,int>
using namespace std;
 
int price[22];
int t, n, m, res;
int map[21][21];
int visited[21][21];
int d[22];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
void bfs(int a, int b) {
    queue<P> q;
    q.push(P(a, b));
    visited[a][b] = 1;
 
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        if (visited[x][y] > n +1) return;
        if (map[x][y]) d[visited[x][y]]++;
 
        for (int i = 0; i < 4; i++) {
            int ax = x + dx[i];
            int ay = y + dy[i];
            if (ax >= 0 && ay >= 0 && ax < n&&ay < n && !visited[ax][ay]) {
                q.push(P(ax, ay));
                visited[ax][ay] = visited[x][y] + 1;
            }
        }
    }
}
 
int get_result() {
    int ans = 0;
    int sum = 0;
    for (int i = 1; i <= n + 1 ; i++) {
        sum += d[i];
        if (price[i] <= sum * m) {
            ans = sum;
        }
    }
    return ans;
}
 
int main() {
    ios_base::sync_with_stdio(false);
 
    for (int i = 1; i <= 21; i++) {
        price[i] = i * i + (i - 1)*(i - 1);
    }
    
    cin >> t;
    for (int tc = 1; tc <= t; tc++) {
        cin >> n >> m;
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> map[i][j];
            }
        }
 
        res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                
            }
        }
        
        res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                bfs(i, j);
                res = max(res, get_result());
                memset(d, 0, sizeof(d));
                memset(visited, 0, sizeof(visited));
            }
        }
        cout << "#" << tc << " " << res << "\n";
    }
}