[SWEA] 2117 : 홈 방범 서비스 - Python

문제

nxn보드, 홈방범 서비스를 제공하기 위해서 운영 비용 필요.
운영비용 = k2 + (k-1)2
홈 방법 서비스를 제공받는 집들은 각각 M의 비용 지불,
구하고자 : 보안회사에서 손해를 보지 않는 한 최대한 많은 집에 홈방법 서비스를 제공하려고 한다. 그때의 제공받는 집들의 수 출력

내 코드

import sys
from collections import deque

sys.stdin = open("input.txt", "rt")

# nxn 보드, 마름모 모양의 영역에서만 자공
# k가 커질수록 운영 비용 증가
# 운영 비용 : k**2 + (k-1) **2
# 운영 비용은 도시를 벗어난 영역에서도 똑같음.

# 홈방법 서비스 제공받는 집들은 각각 m의 비용 지불.
# 보안회사에서는 손해를 보지 않는 한 최대한 많은 집에 홈방법 서비스 제공
# 도시의 크기 n과 하나의 집이 지불할 수 있는 비용 m, 도시 정보가 주어진다.
# 손해를 보지 않으면서 홈방법 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾고
# 그때의 서비스를 제공 받는 집들의 수 출력

# 보안 회사 이익 = m*포함된 집 수 - 운영비용

# 가장 중요한게 손해를 보지 않는 한 최대한 많은 집에 서비스 제공. -> 모두 다 따져봐야 함
# 범위 : 즉, n이 주어지면 중심으로부터 n만큼 퍼져나가야 함.

dx = [-1,0,1,0]
dy = [0,1,0,-1]
def isInner(x,y):
    if 0<=x<n and 0<=y<n:
        return True
    return False
def BFS(startX,startY):
    global maxCnt
    visited = [[False] * n for _ in range(n)]
    visited[startX][startY] = True
    dq = deque()
    dq.append((startX,startY))
    cnt = 0 # 현재의 탐색에서 발견된 집의 개수
    if g[startX][startY] == 1: cnt = 1
    dis = 1 # 중심좌표로부터 거리
    # 크기 1일떄도 검사. (본인 좌표만)
    if cnt * m - 운영비용[1] >= 0:
        maxCnt = max(maxCnt, cnt)

    while dis <= n: # 총 n번 퍼져나가야 함. : 중심으로부터 거리 
        size = len(dq)
        for _ in range(size):
            x,y = dq.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if isInner(nx,ny) and not visited[nx][ny]:
                    visited[nx][ny] = True
                    dq.append((nx,ny))
                    cnt += 1
        # 보안회사의 이익이 0이상이면 갱신 가능
        if cnt * m >= 운영비용[dis+1]:
            maxCnt = max(maxCnt, cnt)
        dis += 1

T = int(input())
for t in range(1,T+1):
    n,m = map(int, input().split()) # n,m : 보드 n, 각 집 m만큼의 비용
    g = [list(map(int, input().split())) for _ in range(n)]
    # 각 좌표에서 n+1만큼 퍼져나가면서 확인
    운영비용 = [k**2 + (k-1)**2 for k in range(0,n+2)]
    maxCnt = 0

    for i in range(n):
        for j in range(n):
            BFS(i,j)
    print(f"#{t} {maxCnt}")

코멘트

문제를 읽어보면 k의 범위를 설정해야 하는 것을 알 수 있다.
k의 크기에 따른 마름모 살펴보면...
k=1 => 1
k=2 => 1
k=3 => 3
k=4 => 3
k=5 => 5
k=6 => 5

즉, 문제에서 주어진 정사각형 n의 크기 +1이 k의 최댓값이 된다.

운영비용은 면적에 따라 동일 -> 미리 구할 수 있음
주의 사항 : 서비스 영역 마름모가 지도를 벗어나더라도 비용은 동일하게 발생한다.

BFS가 사이클 별로 돌았어야 했다. k => 집의 수
현재 k의 영역에 있는 집 대상으로 탐색, 이후 영역 확장.