SWEA 2117 홈 방범 서비스(with Python)

• BFS를 활용해서 filter를 활용하는 느낌으로 풀었다...

• 이 방법보다는 모든 집의 위치와 현재 서비스할 수 있는 범위를 비교하여 집의 개수를 세어주는게 훨씬 속도가 빠르다.

  • 쓸데 없이 비어있는 공간을 셀필요 없기 때문이다.

• 대략 7배 정도 빠르다. (ㅜ 천재들...)

import sys
sys.stdin = open(r'/Users/kangdaeyoung/Downloads/sample_input (4).txt', 'r')

from collections import deque

T = int(input())

for tc in range(1, 1+T):
    # N: 주어진 공간 변 길이, M: 집 1개당 지불 가격
    N, M = map(int, input().split())

    answer = 0

    brd = [list(map(int, input().split())) for _ in range(N)]
    max_homes = 0
    max_earning = 0
    for r in range(N):
        for c in range(N):
            if brd[r][c] == 1:
                max_homes += 1
    max_earning = max_homes * M

    # bfs로 해결하고자 한다.
    # 1. 가장 넓은 방범 서비스를 위해 N이 홀수면 N 짝수면 N+1 로 초기화한다.
    K = N if N%2 else N+1

    is_terminate = False
    for k in range(K, 0, -1):
        # 2. (전체 집 개수 * M) < K**2 (K-1)**2 이면 바로 K를 1씩 줄인다.
        if max_earning < k**2 + (k-1)**2:
            continue
        # 3. 가능한 k 값부터 bfs로 방범 서비스의 손익을 체크해본다.
        for r in range(N):
            for c in range(N):
                visited = [[0]*N for _ in range(N)]
                queue = deque([[r, c]])
                visited[r][c] = 1

                served_homes = 0
                if brd[r][c] == 1:
                    served_homes += 1
                # bfs로 k 방범 서비스 area 안에 속하는 집 개수 구하기
                while queue:
                    # cr => current row
                    cr, cc = queue.popleft()
                    for dr, dc in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                        if (
                            0 <= cr+dr < N and
                            0 <= cc+dc < N and
                            visited[cr+dr][cc+dc] == 0 and
                            abs(cr+dr - r) + abs(cc+dc - c) < k
                        ):
                            queue.append([cr+dr, cc+dc])
                            visited[cr+dr][cc+dc] = 1
                            if brd[cr+dr][cc+dc] == 1:
                                served_homes += 1
                # 같은 서비스 영역(k)으로 맵 전체를 순환한다.
                # 손익 분기점을 넘으면서
                # 서비스 받는 집의 최대 개수를 구한다.
                if served_homes*M >= k**2 + (k-1)**2:
                    is_terminate = True
                    if served_homes > answer:
                        answer = served_homes

        if is_terminate:
            break
    print(f'#{tc} {answer}')