2117.홈 방범 서비스

이번에 풀어볼 문제는 SW Expert 2117 홈 방범 서비스다. 난이도는 역시나 그렇게 어려운 거같진 않지만

이번에 느낀점은 역시 예외상황을 확인하려면 예시를 잘봐야한다.

이 문제에서 나의 실수는 탐색에 있었다. 이 문제는 전부다 탐색을 해봐야 하는데.. 

나는 집위주로만 탐색을 했다. 허허허.. 여튼 다시수정했으니 됐지만...

SW Expert Academy

1. 탐색을 언제 끝마칠지 판단해야함 => 서비스 범위가 맵을 넘어서면 정지

2. 언제 최대값을 가져갈지 생각해야함 => 이득 - 운영비용이 적자가 나지 않으면 해당 값을 최대치와 비교

3. 탐색하는 좌표에 집이 있는 경우 => 집 갯수 +1 

=> 이 경우만 잘구현해주면 굉장히 쉽게 풀리는 문제이다.

 

 

---

 

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
#define MAX 21
using namespace std;
int T, N, M;
 
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
 
int map[MAX][MAX];
int check[MAX][MAX];
queue<pair<int, int>>q;
int answer = 0;
 
void reset_check(){ // check배열과 queue 초기화
    for (int i = 0; i < MAX; i++){
        for (int j = 0; j < MAX; j++){
            check[i][j] = 0;
        }
    }
    int size = q.size();
    for (int i = 0; i < size; i++)
        q.pop();
}
 
void reset(){ // 변화하는 모든 배열과 변수 초기화
    for (int i = 0; i < MAX; i++){
        for (int j = 0; j < MAX; j++){
            check[i][j] = map[i][j] = 0;
        }
    }
    answer = 0;
}
 
int search(int x, int y){ // 탐색
    q.push(make_pair(x, y)); // 시작 좌표 큐에 push
    check[x][y] = 1;         // 시작 좌표 방문
    int house = 0;  // 집 관련 변수
    int k = 1;      //
    if (map[x][y]) // 해당 좌표 map 값이 0보다 크면
        house += 1;// 집이있으니 집갚 +1
    
    while (!q.empty()){ 
        if (k > N + 1) // N+1보다 K값이 커지면
            break;     // 탐색종료
 
        if ((house*M - ((k*k) + (k - 1)*(k - 1))) >= 0) // 집세로 받은 돈보다 운영값이 적으면
            answer = max(answer, house); // 집 갯수 비교후 최대값 저장
        
        int size = q.size(); // 큐에 크기만큼만 탐색
        for (int j = 0; j < size; j++){
            int xx = q.front().first;
            int yy = q.front().second;
            q.pop();
 
            for (int i = 0; i < 4; i++){
                int ax = xx + dx[i];
                int ay = yy + dy[i];
                if (ax < 0 || ay < 0 || ax >= N || ay >= N)
                    continue;
                if (!check[ax][ay]){ // 방문한적없으면
                    q.push(make_pair(ax, ay)); // 방문으로 체크하고
                    check[ax][ay] = check[xx][yy] + 1; // 방범 운영범위 저장( 디버깅하기 좋게)
                    if (map[ax][ay]){ // 방문한 좌표에 집이있으면
                        house += 1; // 집크기 +1
                    }
                }
            }
        }    
        k++; // 방범 운영 범위 증가
    }
    return answer;
}
 
int main(){
    freopen("2117.txt", "r", stdin);
    cin >> T;
    for (int z = 1; z <= T; z++){
        reset();     // 다음 테스트 케이스를 위해 초기화
        int ans = 0;// 정답변수
        cin >> N >> M;
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++)
                cin >> map[i][j]; // 맵에 값 입력받기
        }
 
 
        for (int i = 0; i < N; i++){
            for (int j = 0; j < N; j++){
                ans = max(ans, search(i, j)); // 탐색 후 최대값 저장
                reset_check(); // check 배열만 초기화
            }
        }
        cout << "#" << z << " " << ans << endl;
    }
    return 0;
}