[SWEA] 홈 방범 서비스

[문제]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

SW Expert Academy

 

[풀이]

1) 방범 영역이 퍼져나가는 모양이 BFS같아서 BFS로 접근함. 

 

2) m = 한 집에서 지불하는 비용 

전체 집의 수 *  m 을 max_fee라고 한다면 운영 총 비용(k*k + (k-1)*(k-1))은 max_fee를 초과하면 안된다. 

 

3) k의 크기는 최대 n 

 

4) k의 크기마다 운영비용은 고정되어있기 때문에 실행시간을 줄이기 위해 미리 구해둔다. 

 

5) 기준점이 바뀔 때마다. visited를 새로 생성한다. 

 

6) cnt (현재 영역에 속한 집의 수) * m >= 운영비용 이라면 cnt를 저장하고 이 다음에 나올 cnt와 큰 값과 대소비교 한다. 

 

* 2,3 번 조건은 루프 정지 조건으로 사용함 

* 방범 서비스는 이익이 0이어도 된다. 손해가 아니기 때문에 

 

* makeMemo() => K의 크기에 따른 운영비용을 미리 구해놓고 대소 비교만 한다. 

* 궁금한 점 

visual code가 이상한건지 queue에 pair를 사용하려면 닫는 꺽쇠를 한 칸 띄어서 써야한다. (귀찮..)

 

---

#include <iostream>
#include <queue>
#include <cmath>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
typedef long long ll;
 
//홈 방법 서비스 - BFS
int n, m;
 
int map[21][21];
bool visited[21][21];
int memo[21];
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int ans = 0;
int max_fee = 0;
 
void makeMemo() {
    for (int i = 1; i <= 20; i++) {
        memo[i] = i * i + (i-1) * (i-1);
    }
}
void bfs(int x, int y) {
    int k = 1;
 
    queue<pair<int, int> > q;
 
    q.push(make_pair(x, y));
    
    memset(visited, false, sizeof(visited));
 
    visited[x][y] = true;
 
    int cnt = map[x][y] == 1 ? 1 : 0; //집의 수 
 
    while(!q.empty()) {
        int size = q.size();
 
        if (cnt * m >= memo[k]) {
            ans = max(ans, cnt);
        }
 
        if (k == n+1) return;
 
        if (memo[k] > max_fee) return;
 
        for (int i = 0; i < size; i++) {
            pair<int, int> p = q.front();
            q.pop();
 
            int cx = p.first;
            int cy = p.second;
 
            for (int j = 0; j < 4; j++) {
                int nx = dx[j] + cx;
                int ny = dy[j] + cy;
 
                if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny]) continue;
 
                if (map[nx][ny]== 1) {
                    cnt++;
                }
 
                q.push(make_pair(nx, ny));
                visited[nx][ny] = true;
            }
        }
        k++;
    }
 
}
 
void init() {
    memset(map, 0, sizeof(map));
    
    max_fee = 0;
    ans = 0;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int t;
 
    cin >> t;
    
    makeMemo();
    for (int tc = 1; tc <= t; tc++)
    {
        cin >> n >> m; //m = 한 집당 지불하는 비용
        init();
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> map[i][j];
                if (map[i][j] == 1) {
                    max_fee += m;
                }
            }
        }
        //입력
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                bfs(i, j); //모든 좌표에 대해 탐색 시작
            }
        }
        cout << "#" << tc << " " << ans << '\n';
    }
    return 0;
}