SWEA 2117 : [모의 SW 역량테스트] 홈 방범 서비스

문제

---

 

문제 풀어보기

 

 

풀이

---

 

테스트 케이스를 통과하기 위해 문제 꼼꼼히 읽자!!!

내일 삼성 코테보러갑니다.

ㅈㅅ

 

주의할 점

1. 집이 1개 일수도 있다.

2. 최대 20 x 20 까지의 거리를 보자

3.  거리마다 bfs 하지 말고 한 번에 하고 계산하자.

 

 

 

코드

---

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

using namespace std;
#define safe(x,y) x>=n || x<0 || y<0 || y>=n

int dx[] = { -1 , 1, 0,0};
int dy[] = { 0,0, -1, 1 };
////위 오른쪽 아래 왼쪽

//int dx[] = { -1, 1, 1, -1 };
//int dy[] = { 1, 1, -1 , -1 };
// 대각선

int ansHome; // 선택하는 집의 최대수
int n, m;
int arr[21][21]; // 집 위치
vector<int> pay(50, 0);  // 운용비
int dist[21][21]; // BFS 할때 거리

void bfs(int a, int b) {
	memset(dist, -1, sizeof(dist));
	queue<pair<int, int>> q;
	dist[a][b] = 1;
	q.push({ a,b });
	int maxSz = 0;
	while (!q.empty()) {
		int x, y;
		tie(x, y) = q.front();
		q.pop();
		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (safe(nx, ny)) continue;
			if (dist[nx][ny] != -1) continue;
			dist[nx][ny] = dist[x][y] + 1;
			if (dist[nx][ny] > maxSz) maxSz = dist[nx][ny];
			q.push({ nx,ny });
		}
	}
	// 각 거리마다 수익계산
	int cnt = 0;
	for (int k = 1; k <= maxSz; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (dist[i][j] == k && arr[i][j] == 1) cnt++;
			}
		}
		int result = (m * cnt) - pay[k];
		if (0 <= result) {
			if(ansHome < cnt) ansHome = cnt;
		}
	}

}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int T;
	cin >> T;

	for (int i = 1; i < 50; i++) {
		pay[i] = (i * i) + (i - 1) * (i - 1);
	}

	for (int test = 1; test <= T; test++) {

		cin >> n >> m;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> arr[i][j];
			}
		}
		ansHome = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				bfs(i, j );
			}
		}
		cout << "#" << test << ' ';
		cout << ansHome << endl;

	}

	return 0;
}