[SWEA] 홈 방범 서비스

문제

링크

문제 풀이

😫 처음 시도한 실패한 방법
처음에는 NxN 맵을 모두 돌면서 각 좌표에서 범위가 K일 때 포함되는 집의 수를 세면서 max값을 업데이트 하는 방법을 썼다.
이 방법일 때 알아낸 것은 N일 때 K의 범위는 1부터 N+1이라는 것.
아래 그림을 예로 들면 K가 4일 때 N이 3인 맵을 모두 덮는다

그럼 여기까지만 해도 벌써 for문을 3번 돌게 된다
dfs로 한 중심 좌표에서 K 범위만큼 탐색하는 것을 구현하다가 시간이 너무 오래 걸려서 풀이 방법을 바꾸었다.

💡 성공한 방법
허무하게도 정말 쉬운 방법으로 성공했다.
각 집 사이의 거리를 구해서 K 범위 안에 있으면 count 하는 방식으로 구현했다.

‼️ 문제를 풀면서 주의할 점은 !손해를 보지 않는 서비스 영역을 찾아야 한다! (= 이득이 없어도 된다)

코드

import sys

sys.stdin = open("sample_input.txt", "r")


def get_distance(x, y, home):
    return abs(home[0] - x) + abs(home[1] - y)


def make_diamond(r, x, y):
    global home_count, home_list

    for home in home_list:
        if get_distance(x, y, home) < r:
            home_count += 1


T = int(input())
for test_case in range(T):
    max_home_count = 0
    city_info = list()
    home_list = list()
    N, M = map(int, input().split())
    K = N+2

    for _ in range(N):
        city_info.append(list(map(int, input().split())))

    for i in range(N):
        for j in range(N):
            if city_info[i][j] == 1:
                home_list.append((i, j))

    for i in range(N):
        for j in range(N):
            for k in range(1, K):
                operation_cost = k * k + (k - 1) * (k - 1)
                home_count = 0
                make_diamond(k, i, j)

                # home_count * M - operation_cost : 회사의 이익
                profit = home_count * M - operation_cost
                if -1 < profit:
                    max_home_count = max(max_home_count, home_count)
                    # max_profit = home_count * M - operation_cost

    print("#{} {}".format(test_case+1, max_home_count))