[알고리즘] 홈 방범 서비스

포인트

1. 홈 방범 서비스 -> 각각의 영역을 돌면서 서비스에 최대 값을 찾아준다.

2. bfs를 이용하여 각각의 서비스를 이용할 수 있게 한다.  -> 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

c++/cpp

#include <iostream>
#include <cstring>
#include <queue>
#include <tuple>
 
using namespace std;
 
int n, m, answer;
int map[20][20];
bool visited[20][20];
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
 
 
int calc(int k) {
    return (k * k) + (k - 1) * (k - 1);
}
 
void bfs(int a, int b) {
    queue<pair<int, int>> q;
    q.push(make_pair(a, b));
    visited[a][b] = true;
    int cnt = 0;
 
    if (map[a][b] == 1) cnt += 1;
    int service = 1;
 
    while (!q.empty()) {
        if (service > n + 1)
            break;
        if (cnt * m - calc(service) >= 0) {
            answer = max(answer, cnt);
        }
 
        int size = q.size(); // 턴마다 처리를 해야 한다.
        for (int qs = 0; qs < size; qs++) {
            int x, y;
            tie(x, y) = q.front();
            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) continue; // 범위 체크
                if (!visited[nx][ny]) {
                    q.push(make_pair(nx, ny));
                    visited[nx][ny] = true;
                    if (map[nx][ny] == 1) {
                        cnt += 1;
                    }
                }
            }
        }
        service += 1;
    }
}
 
int main() {
    int testcase;
    cin >> testcase;
    for (int t = 1; t <= testcase; t++) {
        answer = 0;
        memset(map, 0, sizeof(map));
 
        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++) {
                memset(visited, false, sizeof(visited));
                bfs(i, j);
            }
        }
 
        cout << "#" << t << " " << answer << '\n';
    }
 
    return 0;
}

python

import collections

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def calc(k: int) -> int: # 운영비용 계산하기
    return (k * k) + (k - 1) * (k - 1)


def bfs(a: int, b: int):
    global answer
    q = collections.deque() # 큐로 적용하기
    q.append([a, b])
    visited = [[0 for _ in range(n)] for _ in range(n)]
    visited[a][b] = 1

    cnt = 0

    if data[a][b] == 1: # 자기 기본자리 표시
        cnt += 1
    k = 1 # 서비스 영역은 1부터

    while q:
        if k > n + 1: # 서비스 영역이 한변의 길이보다 크면 종료
            break

        if cnt * m - calc(k) >= 0: # 운영비용 계산
            answer = max(answer, cnt)

        size = len(q)
        #  턴마다 처리를 해야 한다
        #  거리를 표시하는 수단 중 하나
        for _ in range(size):
            x, y = q.popleft() 

            for i in range(4): # 방향 델타 사용
                nx = x + dx[i]
                ny = y + dy[i]

                if not (0 <= nx < n and 0 <= ny < n): # 범위 제한
                    continue

                if visited[nx][ny] == 0: # 방문 처리
                    q.append([nx, ny])
                    visited[nx][ny] = 1
                    if data[nx][ny] == 1: #집의 개수 세주기
                        cnt += 1

        k += 1 # 서비스 영역 1 증가


for test in range(1, int(input()) + 1):
    n, m = map(int, input().split()) # n, m

    data = [list(map(int, input().split())) for _ in range(n)] # 데이터 입력

    answer = 0
    for i in range(n):
        for j in range(n):
            bfs(i, j) # 행마다 bfs 를 통해서 각각의 비용을 구한다.

    print('#{} {}'.format(test, answer))