[SWEA][D4][#02117] 홈 방범 서비스

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

문제 생략

My Sol

def main(L):
    global maxV
    for k in range(L, 0, -1):
        for i in range(N):
            for j in range(N):
                subMain(k, i, j)
        if maxV:
            return maxV
    return 1


def subMain(L, ni, nj):
    nowCnt = 0
    for ci in range(ni-L, ni+L+1):
        for cj in range(nj-L, nj+L+1):
            if not (0<=ci<N and 0<=cj<N): continue
            if not mat[ci][cj]: continue
            if L < abs(ni-ci) + abs(nj-cj): continue
            nowCnt += 1
    if nowCnt*M >= costLst[L]:
        global maxV
        maxV = max(maxV, nowCnt)


# costLst
costLst = [0]*40
costLst[0] = 1
i = 1
while i < 40:
    costLst[i] = costLst[i-1]+i*4
    i += 1


T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    mat = [list(map(int, input().split())) for _ in range(N)]

    # 집의 개수 homeCnt
    homeCnt = 0
    for i in range(N):
        for j in range(N):
            if mat[i][j]:
                homeCnt += 1

    # 최대 크기 L
    total = M*homeCnt
    L = 0
    while costLst[L] < total:
        L += 1

    maxV = 0
    print(f'#{tc} {main(L)}')

처음에 중앙으로부터 가장 멀리 갈 수 있는 길이인 L을 인덱스로 하는 costLst를 만들어, while문으로 L에 따른 범위의 비용을 계산해주었다. 그리고 전체 집의 개수를 세어 M을 곱한 값보다 넓이가 클 수 없기 때문에 while문을 이용해 가장 큰 넓이를 허용하는 L을 구하였다.

이후 main() 함수를 실행해주는데, 이 함수는 L부터 시작해서 0까지, 2차원 배열의 각 칸을 돌며 주변 범위에 대해 손해를 보는지, 보지 않는지를 체크하는 함수이다. 이 함수 내의 L부터 시작하는 k마다 전역변수 maxV가 0이 아닌지를 체크하는데, 만약 어떤 k에서 면적에 비해 집의 개수가 충분해서 손해를 보지 않는다고 판단되면 집의 개수를 구해 maxV와 비교해 더 큰 값을 maxV로 갱신한다. 이는 k가 같은 경우, 모든 2차원 배열을 돌면서 가장 집을 많이 포함할 수 있는 좌표점의 집의 개수를 최대로 갱신하기 위함이다.

그 각각의 기준점마다 범위 내의 집을 체크하고, 손해를 보는지를 체크하는 함수가 subMain() 함수이다. main()함수의 각 k, i, j마다 호출되는 이 함수의 주요 역할은 범위 내의 집의 개수를 세는 것이다. 주목해야할 점은 현재 기준점이 ni, nj일 때 ni-L부터 ni+L까지, nj-L부터 nj+L까지의 범위 내에 마름모 범위가 확실히 들어가는 것이다. 때문에 이 범위 내의 각각의 좌표를 ci, cj로 두고 아래의 사항을 확인한다.

1. ci, cj가 0부터 N-1의 인덱스 범위를 넘지 않는지
2. mat[ci][cj]가 0이 아닌, 1로서 집이 맞는지
3. ni와 ci, nj와 cj의 합, 즉 거리가 L보다 크지는 않는지

위의 3가지를 모두 만족한다면 마름모 범위 내의 집이므로 nowCnt를 1 올려준다. 이렇게 모든 칸을 조회하여 nowCnt를 구하면, 이 개수와 집당 금액인 M을 곱한 값이 현재 L에 대한 범위 비용 costlst[L] 보다 크거나 같다면 maxV를 nowCnt와의 비교로 더 큰 값으로 갱신해주는 것이다.

아쉬운 점은 마름모의 크기에 비해 조사하는 범위는 2배이기 때문에 배열이 커질수록 불필요한 연산이 많아지지만, 코드가 직관적이기 때문에 위와 같이 작성하였다.

결과

PASS