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

🔗 문제

SW Expert Academy

SW Expert Academy

 

 

✏️ 풀이

실수한게 많아서 시간을 들여 풀이를 써보고자 한다.

 

 

문제 내용

도시의 크기 N과 하나의 집이 지불할 수 있는 비용 M, 도시의 정보가 주어진다. 이때, 손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾고, 그 때의 홈방범 서비스를 제공 받는 집들의 수를 출력하는 프로그램을 작성하라

• 비용(cost ) : (i*i) + (i-1) * (i-1) // i가 범위일 때
• 수익(profit) : 범위 내의 집의 수(cnt) * M

 

 

손해를 보지 않으려면 아래 조건을 만족해야 한다.

cost - profit >= 0 // 0도 포함해야한다! 음수가 아니니까!!!

 

 

 

range를 증가해야하는데 어느 범위까지 보면 좋을까?

집들의 개수를 구하면 바로 알 수 있다.

모든 집을 돈다고 해도 범위가 너무 커져서 비용을 초과해버리면 더 이상 범위를 키울 필요가 없다

cost > 모든 집의 수 * M

 

 

나는 이 아이디어로 바로 문제를 시작했다. (삽질의 시작)

 

👎 시간초과 풀이

 

기본적으로 BFS와 가지치기가 있는 backtracking 으로 시도를 했다. 

 

문제에서 배열의 범위가 벗어난 곳까지 비용처리를 하기 때문에 set<pair<int, int> > 를 사용해보았다.

이렇게 하면 배열의 음수 범위를 신경쓰지 않아도 되기 때문에 도전해봤다! 

 

아이디어 1

집에서 부터 BFS를 시작한다.

하지만 아래 예제(2) 를 보자. 정중앙에서 시작하는게 맞다. 집부터 시작하면 구할 수 없다.

1
7 7
0 0 0 1 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
1 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 1 0 0 0

 

 

아이디어2

모든 위치에서 BFS를 돌자.

답은 나오지만 시간 초과가 떴다.

 

 

BFS가 시간 초과의 원인

bfs를 하게 되면 집이 아닌 곳도 queue에 넣어주고 돌아 봐야하기 때문에 비효율적이다.

이 방법이 아니면 못 구하는 줄 알았는데 아니었다.

 

 

 

---

🧠 문제를 풀면서 배운 점

 

1. BFS가 아닌 맨하탄 거리로 범위 이용하기

이런 주어진 “범위”가 있고 범위 내의 조건이 필요할 땐 이 방법도 있다는 걸 잘 기억하길 바라며 쓴다..

거꾸로 발상해보면 현재 위치와 집의 위치만 비교하면 된다는 걸 깨달아야 한다. 그냥 이게 문제의 포인트다.

 

문제에서 필요한 것은 현재 범위 내의 집의 개수

N*N으로 정해져있는 맵에 비하면 집의 개수는 1개에서 최대 40개!

 

내 위치와 모든 집의 위치를 비교해서 현재 range 내의 집의 개수를 효율적으로 셀 수 있다.

if(std::abs(x-_x) + std::abs(y-_y) < range)

이렇게 하면 BFS 보다 연산 횟수를 적게 하며 원하는 답을 얻을 수 있다.

---

2. 반복되는 연산 저장해서 시간 아끼기

cost[range]는 i, j와 달리 정해져있으므로 미리 구한 후 재사용하여 시간을 아끼자

 

 

---

➕ 집은 어떤 자료구조에 넣는게 가장 빠를까?

list, set , vector 순으로 돌려봤는데 vector가 제일 빨랐다.🤟🏻

 

 

💾  소스

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
 
using namespace std;
 
typedef std::pair<int, int> pii;
 
const int MAX = 22;
int cost[MAX] = {0, };
int N, M, answer;
int max_cost;
std::vector<pii> house;
 
// 현 위치에서 k 범위 봤을 때 집의 개수
int countMaxHouse(const int _x, const int _y, const int range)
{
    int result = 0;
     
    for(const auto& [x, y] : house)
    {
        if(std::abs(x-_x) + std::abs(y-_y) < range)
        {
            ++result;
        }
    }
     
    return result;
}
 
void solve(const int x, const int y)
{
    for(int range = 1; range <= MAX; ++range)
    {
        if(cost[range] > max_cost) return;
         
        // 현 위치에서 range 범위만큼 봤을 때 집의 개수
        int result = countMaxHouse(x, y, range);
        if(result*M - cost[range]>= 0)
            answer = (answer > result ? answer : result);
 
    }
}
 
 
int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
     
    for(int i=1; i<=MAX; ++i)
    {
        cost[i] = (i*i) + (i-1) * (i-1);
    }
     
    int T, input;
    std::cin >> T;
    for(int tc=1; tc<=T; ++tc)
    {
        //input
        std::cin >> N >> M;
         
        for(int i=0; i<N; ++i)
        {
            for(int j=0; j<N; ++j)
            {
                std::cin >> input;
                 
                if(input == 1)
                    house.push_back({i, j});
            }
        }
         
         
        answer = 0;
        max_cost = house.size() * M;
         
        //집이 아니라 모든 위치에서 해봐야한다.
        for(int i=0; i<N; ++i)
        {
            for(int j=0; j<N; ++j)
            {
                solve(i, j);
            }
        }
         
        house.clear();
 
        std::cout << "#" << tc << " " << answer << "\n";
    }
     
    return 0;
}