2117. 홈 방범 서비스

static int board[20][20];
static int N, M;
static int table[21];
static int d[4][2] = {
	-1, 0,
	1, 0,
	0, -1,
	0, 1
};

typedef struct
{
	int y, x, k;
}base;

static void table_init()
{
	int cover = 1;
	for (int i = 1; i <= 20; i += 2)
	{
		table[i] = cover;
		table[i + 1] = cover;
		cover += 2;
	}
}

static bool out_of_bound(int y, int x)
{
	if (y < 0 || y >= N)
		return true;
	if (x < 0 || x >= N)
		return true;
	return false;
}

static int get_home(int y, int x, int k)
{
	int ret = 0;
	queue<base> q;

	q.push({ y, x, k });
	for (int i = 1; i < k; i++)
	{
		//좌우로만 움직이기 때문에, d를 사용할 필요는 없다.
		if (x - i >= 0)
			q.push({ y, x - i, k - i });
		if (x + i < N)
			q.push({ y, x + i, k - i });
	}
	while (q.size())
	{
		base b = q.front();
		q.pop();

		int cy = b.y, cx = b.x;
		//center이므로 한번만 처리해야됨
		//커버할 수 있는 곳에 집이 있다면
		if (board[cy][cx])
			ret += 1;

		for (int dir = 0; dir < 2; dir++)
		{
			int ny = cy, nx = cx; //center 좌표	
			for (int i = 1; i < b.k; i++)
			{
				ny += d[dir][0];
				nx += d[dir][1]; 
				if (out_of_bound(ny, nx))
					break;
				if (board[ny][nx])
					ret += 1;
			}
		}
	}

	return ret;
}

static int solution()
{
	int ret = 0, tot = 0;

	scanf("%d %d", &N, &M);
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			scanf("%d", &board[y][x]);
			tot += board[y][x]; //전체 집 개수
		}
	}

	if (M - 1 >= 0) //k가 1인 경우는 쉽게 파악 가능
		ret = 1;

	int maximum = table[N];
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			for (int k = 2; k < maximum; k++)
			{
				int operating = k * k + (k - 1) * (k - 1); //운영비,
				//y, x 위치에 k영역의 서비스 설치 시 서비스를 할 수 있는 집의 개수
				int nr_home = get_home(y, x, k);
				//손해가 아니다 -> 최소한 이득은 없어도 된다.
				if (M * nr_home - operating >= 0 && nr_home > ret)
					ret = nr_home;
			}
		}
	}

	int operating = maximum * maximum + (maximum - 1) * (maximum - 1);
	int nr_home = tot;
	if (M * nr_home - operating >= 0 && nr_home > ret)
		ret = nr_home;

	return ret;
}

손해가 아니라는 것은 적어도 이득은 없다가 되기 때문에 이득이 0 이상이 되어야 한다.

 

이 문제 풀이에서는 서비스 중심 위치를 모든 x,y 좌표에 대해서 그 커버를 2 부터 maximum보다 작을 때 까지 반복하는 전수조사를 해본다. 이것이 가장 정확하기 때문이다.

 

그리고 서비스 커버 영역을 설정하면서 해당 서비스 영역에 집이 존재하는지 확인 함으로서 서비스 영역 설치 시 최대 몇 가구나 서비스를 받을 수 있는지 확인 할 수 있다.

 

마지막으로 bfs를 위해 초기 좌표를 준비 할 때, 중심으로 부터 좌, 우로만 이동하면서 배열 내에 존재 하는지 확인하는데, 이 좌표들을 이후 위,아래로 다시 움직이는 과정에서 그 중심 좌표가 두번 체크 될 수 있다는 것에 유의해야 한다.

 

 

//주의사항 및 정리

1. 여기에서는 visit을 따로 정의하지는 않았지만, 실제 시험 시에는 일단 정의 해둘 것.

2. 최대, 최소는 항상 가능한 모든 경우를 체크하는 것이 정확하므로 의심하지 말고 코드를 작성할 것.