[SWEA] 2117. [모의 SW 역량테스트] 홈 방범 서비스

📚 문제

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}')

🔍 결과