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

SWExpertAcademy의 홈방범서비스(2117) 문제이다.

[ 문제풀이 ]

1) 본인은 먼저 이 문제를 모든 좌표에서, 서비스 할 수 있는 최대영역까지 탐색을 반복하면서 집의 갯수를 구해 보았다.

    탐색은 BFS 알고리즘을 사용해 보았다.

    BFS를 탐색하는 부분에 대해서 구체적으로 알아보도록 하자.

    BFS Leveling Skill을 이용해서 Service영역이 1일때부터 N + 1일때까지를 탐색을 반복하면서 회사가 이득을 볼 수 있는

    조건 내에서 최대의 집의 갯수를 구해보았다.

    그런데 탐색 영역이 왜 1부터 N+1까지일까? 맵의 크기는 N인데 왜 탐색은 N+1까지일까??

    아래의 그림을 보고 오도록 하자.

   

     < 사진 출처 및 정보 제공 : LeeyunTiger(계란후라이) 님. >

     위의 사진에서 파랑색은 K = 1일때 서비스영역, 빨강색은 K = 2일때, 하늘색은 K = 3일때, 초록색은 K = 4일 때 영역이고

     노랑색은 K = 5일때 영역이다. 그리고 검은색으로 테두리 쳐진 4x4 짜리 맵을 한번 잘보자.

     검은색 테두리를 우리가 입력받은 맵이라고 생각하고 보면 N = 4가 된다.

     이 때, 서비스영역인 K = 4일때까지만 하면 모든 칸을 다 탐색할 수 있을까??

     아니다. 가장 오른쪽 아래 빨강색으로 적힌 '3'에 주목하자. 저 '3'이 있는 칸은 K = 5일때 서비스 받을 수 있는 영역이다.

     즉, 우리는 탐색을 할 때에 N + 1 영역까지 K값을 증가시키면서 탐색을 해 주어야 N x N 에 존재하는 모든 칸들을 다

     탐색할 수 있게 되는 것이다.

2) 뭐 따로 주의해야할 부분은 없는 것 같다. 단지 모든 좌표에서 탐색하는 만큼 Visit배열을 초기화시켜주는 것 정도만

    주의해주면 될 것 같다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 20
using namespace std;
 
int N, M, Answer;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Initialize()
{
    Answer = 0;
    memset(MAP, 0, sizeof(MAP));
    memset(Visit, false, sizeof(Visit));
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
int Company_Benefit(int k)
{
    return (k * k) + (k - 1)*(k - 1);
}
 
void BFS(int a, int b)
{
    int House_Cnt = 0;
    queue<pair<int, int>> Q;
    Q.push(make_pair(a, b));
    Visit[a][b] = true;
 
    if (MAP[a][b] == 1) House_Cnt++;
    int Service = 1;
 
    while (Q.empty() == 0)
    {
        if (Service > N + 1) break;
        if (House_Cnt * M - Company_Benefit(Service) >= 0) Answer = Bigger(Answer, House_Cnt);
        int S = Q.size();
 
        for (int Qs = 0; Qs < S; Qs++)
        {
            int x = Q.front().first;
            int y = Q.front().second;
            Q.pop();
 
            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)
                {
                    if (Visit[nx][ny] == false)
                    {
                        Visit[nx][ny] = true;
                        Q.push(make_pair(nx, ny));
                        if (MAP[nx][ny] == 1) House_Cnt++;
                    }
                }
            }
        }
        Service++;
    }
}
 
void Solution()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            memset(Visit, false, sizeof(Visit));
            BFS(i, j);
        }
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}