CS/Algorithm
[SWEA][C++] 2117 홈방범서비스
별토끼.
2019. 3. 9. 16:15
반응형
[SWEA][C++] 2117 홈방범서비스
문제
SW Expert Academy 2117 홈방범서비스
(출처 : https://www.swexpertacademy.com/main/main.do)
풀이
범위때문에 머리가 아팠던 문제입니다ㅠㅠ 범위에 주의해서 다시 풀어봐야겠어요.
우선 범위에 따른 비용은 고정이기 때문에 미리 구하도록 합니다.
그 다음, 칸마다 범위를 넓혀가면서 범위값(dis)에 따른 집의 수를 구해주는데 이는 bfs로 넓혀가기때문에 visited배열로 측정한 거리를 활용하면 됩니다.
범위를 모두 넓힌 후 (k*k+(k-1)*(k-1)) - (m * 집의 수) 값을 계산해야 합니다. 이 값은 dis배열의 범위를 넓히며 sum값을 구한 뒤 위 (k*k+(k-1)*(k-1)) - (m * 집의 수) > 0 일 경우 res변수에 저장합니다.
코드
#define _CRT_SECURE_NO_WARNINGS
#include <memory.h>
#include <cstdio>
#include <queue>
using namespace std;
int m, n;
int map[21][21];
int visited[21][21];
int dis[22];
int price[22];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int max_res = 0;
void BFS(int a, int b) {
queue<pair<int, int>> q;
q.push(make_pair(a, b));
visited[a][b] = 1;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (visited[x][y] > n + 1) return;
if (map[x][y]) {
dis[visited[x][y]]++;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
if (!visited[nx][ny]) {
q.push(make_pair(nx, ny));
visited[nx][ny] = visited[x][y] + 1;
}
}
}
}
void getResult() {
int sum = 0;
int res = 0;
for (int i = 1; i <= n + 1; i++) {
sum += dis[i];
if (price[i] - (m * sum) <= 0) {
res = sum;
}
}
if (max_res < res) {
max_res = res;
}
}
int main() {
int T;
scanf("%d", &T);
for (int i = 1; i <= 21; i++) {
price[i] = (i * i) + (i - 1)*(i - 1);
}
for (int t = 1; t <= T; t++) {
max_res = 0;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &map[i][j]);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
memset(dis, 0, sizeof(dis));
memset(visited, 0, sizeof(visited));
BFS(i, j);
getResult();
}
}
printf("#%d %d\n", t, max_res);
}
}
반응형