[SWEA] 2117. [シミュレーションソフトウェア機能テスト]ホーム防犯サービス

📚 質問する

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu&categoryId=AV5V61LqAf8DFAWu&categoryType=CODE&problemTitle=%ED%99%88+%EB%B0%A9%EB%B2%94+%EC%84%9C%EB%B9%84%EC%8A%A4&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1
これはBFSの問題です.
利用者を含む配列を作成し,各サービス領域に入れる.

上の図に示すように、各数字に人がいる場合は、カウント順に数値値に1を加算します.
拡張に伴い1を増やす必要があるのでBFS探索を行う.
そして最終的に累計合計の面積使用者の総人数を求める.
また、サービス提供コストと運用コストとの差が正の値であれば、サービス面積が最大の場合、サービスの合計人数を出力する.
すべての開始点で上記の操作を繰り返します.

📒 コード#コード#

from collections import deque


def bfs(start_y, start_x):      # BFS 탐색
    queue = deque()
    queue.append((start_y, start_x, 1))     # 시작점을 큐에 담는다, 서비스 영역도 담는다.
    visited[start_y][start_x] = 1
    k_arr[1] = arr[start_y][start_x]
    while queue:
        y, x, k = queue.popleft()
        for i in range(4):          # 네 방향 탐색
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < n and 0 <= nx < n and visited[ny][nx] == 0:
                visited[ny][nx] = visited[y][x]
                k_arr[k + 1] += arr[ny][nx]  # 집의 수를 더한다.
                queue.append((ny, nx, k + 1))       # 서비스 영역을 넓혀서 큐에 담는다.


def house_max():    # 가장 많은 집을 서비스할 수 있는 경우를 찾는다.
    global result
    house_cnt = 0
    for i in range(1, n * 2):
        k = i
        house_cnt += k_arr[i]       # 누적합으로 적어준다.
        if m * house_cnt - (k * k + (k - 1) * (k - 1)) >= 0:    # 적자나지 않는 경우
            result = max(result, house_cnt)


for tc in range(1, 1 + int(input())):
    n, m = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    result = 0
    dy = [0, 1, 0, -1]      # 우 하 좌 상
    dx = [1, 0, -1, 0]
    for i in range(n):      # 모든 좌표에서 시작한다.
        for j in range(n):
            k_arr = [0 for _ in range(n * 2)]       # 서비스 영역의 크기별 집의 수
            visited = [[0] * n for _ in range(n)]   # 방문 여부 확인
            bfs(i, j)           # BFS 탐색
            house_max()         # 가장 많은 수의 집에 서비스할 수 있는 경우
    print(f'#{tc} {result}')

🔍 結果