홈 방범 서비스_2117

문제 출처 : 홈방범서비스_2117

파라미터 정리

NxN 전체 맵 크기 (5 ~ 20)
0 : 빈 칸
1 : 집이 있는 위치
방범 서비스는 마름모 모양의 영역에만 제공
K(영역 크기)에 따라 운영 비용 요구됨 (1 ~ K)
K = K x K + (K - 1) x (K - 1), (예: K=1 -> 비용=1, K=2 -> 비용=5, K=3 -> 비용=13)
서비스 영역이 맵 범위를 벗어나더라도 운영 비용은 변경되지 않음
M 각 집이 지불할 수 있는 비용 (1 ~ 10)
회사의 이익 = Mx(서비스 영역 내 집) - 운영비용
원하는 것 = 회사에서 손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역 찾기
이때 서비스를 제공 받는 집의 수를 출력

간략한 과정

input_1 테스트 케이스의 개수 T 입력받기 (1~T~50)
input_2_1 N,M 입력받기
input_2_2 맵 정보 Map[20][20] 입력받기
(input_2는 T크기 만큼 반복함)
for(int k = 0; k <= N; k++){
//k는 서비스 영역을 의미함, 최대 N사이즈까지 만들 수 있음, 그 이상은 의미 없음
(r,c)는 중간에서 좌상우하 한칸씩 이동하면서 탐색하기
서비스 영역 내 집 개수의 최댓값 구하기
k가 바뀌기 전 회사의 이익을 계산함
회사 이익이 0이상이면 res = max(res, 현재 집 개수) 실행
다음 k로 넘어감
}
output "#n"+ " " + res 출력하기

코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

int T,N,M;
int Map[20][20];
bool visited[20][20];
int Dr[4] = {0,1,0,-1};
int Dc[4] = {-1,0,1,0};

int solve(){
    int res = 0;
    //모든 영역에 대해서 검사
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            memset(visited, false, sizeof(visited));
            //BFS
            int h_cnt = 0;
            queue<pair<int,int>> myqueue;
            myqueue.push(make_pair(i,j));
            visited[i][j] = true;
            if(Map[i][j] == 1) h_cnt++;
            int size = 1;
            //k 사이즈를 증가시키면서 모든 구간 탐색
            while(!myqueue.empty()){
                if(size > N+1) break;//유의미한 범위를 벗어나면
                int cost = (size * size) + (size - 1)*(size - 1);
                int bene = h_cnt*M;
                //손해x -> 최댓값 비교
                if(cost <= bene) res = max(res,h_cnt);
                int q_size = myqueue.size();
                for(int k = 0; k < q_size; k++){
                    int r = myqueue.front().first;
                    int c = myqueue.front().second;
                    myqueue.pop();
                    
                    for(int t = 0; t < 4; t++){
                        int nr = r + Dr[t];
                        int nc = c + Dc[t];
                        if(nr < 0 || nc < 0 || nr > N-1 || nc > N-1) continue;
                        if(visited[nr][nc]) continue;
                        if(Map[nr][nc] == 1) h_cnt++;
                        visited[nr][nc] = true;
                        myqueue.push(make_pair(nr,nc));
                    }
                    
                }
                size++;
            }
        }
    }
    
    return res;
}

int main()
{
    cin >> T;
    for(int t = 0; t < T; t++){
        cin >> N >> M;
        for(int i = 0; i < N; i++){
            for(int  j = 0; j < N; j++){
                cin >> Map[i][j];
            }
        }
        cout << "#" << t+1 << " " << solve() << endl;
    }

    return 0;
}

시행착오

테스트케이스는 통과하지만, 제출 시 시간초과 발생

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

struct loc{
    int r,c,d;  
};

int N,M,T;
int map[50][50] = {0};

int dR[4] = {0,1,0,-1};
int dC[4] = {1,0,-1,0};

int solve(){
    int res = 0;
    
    for(int d = 0; d <= N; d++){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                
                int cost = d*d + (d+1)*(d+1);
                int cnt = 0;
                bool visit[50][50] = {false,};
                
                queue<loc> list;
                list.push({i,j,0});
                
                do{
                    loc curr = list.front();
                    list.pop();
                    
                    visit[curr.r][curr.c] = true;
                    
                    if(map[curr.r][curr.c] == 1) cnt++;
                    if(curr.d >= d) continue;
                    
                    for(int n = 0; n < 4; n++){
                        int nr = curr.r + dR[n];
                        int nc = curr.c + dC[n];
                        
                        if(nr < 0 || nc < 0 || nr > N-1 || nc > N-1) continue;
                        if(visit[nr][nc]) continue;
                        
                        list.push({nr,nc,curr.d+1});
                        visit[nr][nc] = true;
                    }
                }while(!list.empty());
                
                if(cost <= cnt*M) res = max(res, cnt);
            }
        }
    }
    
    
    return res;
}


int main() {
    
    cin >> T;    
    
    for(int t = 0; t < T; t++){
        
        cin >> N >> M;
        
        memset(map,0,sizeof(map));
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                cin >> map[i][j];
            }
        }
        
        cout << "#" << t+1 << " " << solve() << endl;
    }
      
    
    return 0;
}

T = 1인 예제
1
8 3
0 0 0 0 0 1 0 0
0 1 0 1 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0
0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 0
1 0 0 0 0 0 0 0