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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

SW Expert Academy

<풀이>

1. 모든 도시 좌표에서 서비스 제공을 시작한다.

2. 각 좌표에서 시작해서 서비스 영역을 넓혀가며, 그 때 마다 이윤을 구하고 최댓값을 저장한다.

3. 결과를 출력한다.

 

<해법>

1. 각 좌표에서 서비스 영역을 넓혀가는 방법.

=> 각 좌표에서 넓혀지는 서비스 영역이, 2차원 배열에서 BFS를 이용해 4방향 탐색하는 방식과 비슷하다고 생각하였습니다. 따라서 저는 위 방법을 이용하여 구현하였습니다.

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
 
struct pos {
    //좌표
    int x, y;
};
 
//4방향
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int N, M;
int map[20][20];
bool visited[20][20];
int res;
 
//범위 내에 있는지 판단
bool inner(int x, int y) {
    if (x < 0 || y < 0 || x >= N || y >= N) {
        return false;
    }
    return true;
}
 
int bfs(pos str) {
 
    //초기화
    memset(visited, false, sizeof(visited));
 
    queue<pos> q;
    q.push(str);
    visited[str.x][str.y] = true;
 
    int K = 0, cnt = 0, MAX = 0;
 
    while (!q.empty()) {
        int qsize = q.size();
        K++;
        
        //서비스 영역부분 탐색
        for (int i = 0; i < qsize; i++) {
            pos cur = q.front();
            q.pop();
 
            //집 개수 세기
            if (map[cur.x][cur.y] == 1) {
                cnt++;
            }
 
            //4방향 탐색
            for (int j = 0; j < 4; j++) {
                pos nxt = cur;
                nxt.x += di[j];
                nxt.y += dj[j];
 
                if (!inner(nxt.x, nxt.y)) {
                    continue;
                }
                if (visited[nxt.x][nxt.y]) {
                    continue;
                }
                
                q.push(nxt);
                visited[nxt.x][nxt.y] = true;
            }
        }
 
        //이윤 계산
        int profit = (cnt * M) - ((K * K) + (K - 1) * (K - 1));
        
        //손해보지 않는 경우, 집 개수 계산
        if (profit >= 0) {
            if (cnt > MAX) {
                MAX = cnt;
            }
        }
    }
 
    return MAX;
}
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        memset(map, 0, sizeof(map));
        res = 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++) {
                pos str = { i,j };
                int tmp = bfs(str);
 
                if (tmp > res) {
                    res = tmp;
                }
            }
        }
 
        //출력
        cout << "#" << test_case << " " << res << "\n";
    }
 
    return 0;
}

 

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