SW Expert Academy 2117. [모의 SW 역량테스트] 홈 방범 서비스 풀이 With Python

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu&categoryId=AV5V61LqAf8DFAWu&categoryType=CODE

SW Expert Academy

문제의 핵심은 손해를 보지 않으면서 홈 방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾았을 때,

그때의 서비스를 제공받는 집들의 수를 찾는 것이다. 먼저 도시의 집의 개수를 입력받아서 서비스 영역의 운영비용을 손해 보지 않는 선에서 탐색을 진행한다.  그리고 맵의 각 포인트마다 서비스 영역을 탐색하여 서비스를 손해보지 않으면 정답 값과 비교해서 더 큰 것으로 정답 값을 경신하였다. 아래는 해결한 코드이다.

def solution(map1, n, m, homes):
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    answer = 0
    k = 1
    while k * k + (k - 1) * (k - 1) <= homes * m:
        for i in range(n):
            for j in range(n):
                sub = 0
                for x in range(-(k - 1), k):
                    for y in range(-(k - 1), k):
                        if -1 < i + x < n and -1 < j + y < n and abs(x) + abs(y) <= k - 1:
                            if map1[i + x][j + y] == 1:
                                sub += 1
                if sub * m >= k * k + (k - 1) * (k - 1) and answer < sub:
                    answer = sub
        k+=1
    return answer


t = int(input())
for test in range(1, t + 1):
    n, m = map(int, input().split())
    map1 = []
    homes = 0
    for _ in range(n):
        s = list(map(int, input().split()))
        for i in range(n):
            if s[i] == 1:
                homes += 1
        map1.append(s)
    ans = solution(map1, n, m, homes)
    print('#{} {}'.format(test,ans))