[swea 2117] 홈 방범 서비스

분류 : 구현

 

요구사항

회사가 손실보지 않고 서비스를 제공해줄 수 있는 최대 집의 갯수 구하기

 

풀이

맨 처음에 구역의 모양을 보니 bfs처럼 생겨서 bfs로 풀었더니 시간초과가 나서 한참을 고민했다

 

1. 처음 시작할 때 거리를 먼저 정한다.

2. 연산을 시작할 정점을 정한다

3. 집~정점 까지의 거리가 1번에서 정한 거리 이내라면 서비스를 제공해줄 수 있는 집이다

 

이렇게 하면 쉽게 

20*20*21*10라는 아주 작은 시간복잡도로 풀 수 있다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <string.h>
#include <math.h>
using namespace std;

struct go{
	int x;
	int y;
};
int ans=0;
int anshome=0;
int n,m;
int map[22][22];
int visit[22][22];
int dr[4] = {-1,0,1,0};
int dc[4] = {0,-1,0,1};
vector<go> v;

void solve(){
	for(int i=0 ; i < n ; i++){
		for(int j=0 ; j < n ; j++){
			for(int k=1 ; k<= n+1; k++){
				int cnt=0;
				int now = (k*k) + (k-1)*(k-1);
				for(int l=0 ; l < v.size() ; l++){
					int dist = abs(i-v[l].x) +abs(j-v[l].y);
					if(dist< k){
						cnt++;
					}
				}
				int money = cnt*m;
				if(money - now >=0){
					ans=max(ans,cnt);
				}
				
			}
		}
	}
}
int main(){
	int t;
	scanf("%d",&t);
	for(int tc=1;tc<=t;tc++){
		ans=0;
		v.clear();
		scanf("%d%d",&n,&m);
		for(int i=0 ; i < n ; i++){
			for(int j=0 ; j < n ; j++){
				scanf("%d",&map[i][j]);
				if(map[i][j]==1) v.push_back({i,j});
			}
		}

		solve();
		printf("#%d %d\n", tc,ans);
	}
}