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

두 번째 풀이입니다. 예전과는 어떻게 얼마나 달라졌는지 궁금해서 한번 더 풀어보았습니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu&categoryId=AV5V61LqAf8DFAWu&categoryType=CODE&problemTitle=2117&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

<풀이>

1. 도시 정보를 입력받는다.

2. 손해를 보지 않으면서 가장 많은 집들에게 서비스를 제공할 수 있는 영역을 찾고, 그 때 서비스를 받는 집들의 수를 출력한다.

 

<해법>

1. 마름모 서비스 영역을 찾는 방법

=> 저는 마름모 모양으로 커지는 모습이 BFS가 탐색하는 모습과 유사하다고 생각하여서, BFS를 이용하여 단계별로 탐색하였습니다.

 

2. 어떻게 탐색해야할까?

=> 그리디한 해법이나, 최적화 할 수 있는 방법이 없다고 생각합니다. 따라서, 모든 경우를 다 해보아야합니다. 저는 도시의 모든 지점을 탐색하였고, 지점마다 도시가 전부 덮힐때까지 마름모를 넓혀나갔습니다.

 

#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
 
using namespace std;
 
struct pos {
    int x, y;
};
 
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
int N, M;
int map[20][20];
bool visited[20][20];
int answer;
 
bool isInner(pos p) {
    if (p.x < 0 || p.y < 0 || p.x >= N || p.y >= N) return false;
    return true;
}
 
int findServiceArea(pos p) {
    queue<pos> q;
    bool visited[20][20];
    memset(visited, false, sizeof(visited));
 
    q.push(p);
    visited[p.x][p.y] = true;
    int k = 1;
    int people = 0;
    int output = 0;
 
    while (!q.empty()) {
        int qsize = q.size();
        while (qsize--) {
            pos cur = q.front();
            q.pop();
 
            if (map[cur.x][cur.y] == 1) people++;
 
            for (int i = 0; i < 4; i++) {
                pos nxt = cur;
                nxt.x += dx[i];
                nxt.y += dy[i];
 
                if (!isInner(nxt) || visited[nxt.x][nxt.y]) continue;
 
                q.push(nxt);
                visited[nxt.x][nxt.y] = true;
            }
        }
 
        int cost = k * k + (k - 1) * (k - 1);
        if (people * M >= cost) output = people;
        k++;
    }
 
    return output;
}
 
void solution() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            answer = max(answer, findServiceArea({ i, j }));
        }
    }
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        N = 0, M = 0;
        memset(map, 0, sizeof(map));
        answer = 0;
 
        //입력
        cin >> N >> M;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> map[i][j];
            }
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

BFS에 대해 알아볼 수 있는 문제였습니다.