[SWEA][C++] 2117 홈방범서비스

[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);
    }
}