[SWEA 2117] 홈 방범 서비스

첫 번째 접근

모든 위치에 대해 BFS를 진행하였다. BFS를 하면서 집의 개수를 카운트하였고 집의 개수 x M이 운영비용보다 같거나 클 때 최댓값 비교를 진행했다.

PASS는 되었지만 시간이 오래 걸렸고 불필요한 곳까지 탐색한다는 것을 알았다.

 

첫 번째 구현

- K를 N+1 ~ 1까지 탐색하면서 모든 좌표에 대해 BFS를 진행한다.

- BFS는 현재 위치를 기준으로 거리를 통해 방문표시를 한다.

- 거리가 K이하일 때만 큐에 넣어 다음 위치를 탐색할 수 있도록 하였다. => 마름모 형태

- 이후 현재 위치가 집일 경우 집의 개수인 count를 증가시켰다.

- BFS가 종료되고 count x M이 운영 비용보다 크거나 같을 때 최댓값 비교를 한다.

from collections import deque

def check_range(y, x):
    return (0 <= y < N) and (0 <= x < N)

def bfs(y, x, k, cost):
    global answer
    q = deque()
    dist = [[ 0 for _ in range(N)] for _ in range(N)]
    count = 0
    dist[y][x] = 1
    q.append((y, x))

    while q:
        cy, cx = q.popleft()
        if board[cy][cx] == 1:
            count += 1
        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx) and dist[ny][nx] == 0:

                dist[ny][nx] = dist[cy][cx] + 1
                if dist[ny][nx] <= k:
                    q.append((ny, nx))

    pay = count * M
    if pay >= cost:
        answer = max(answer, count)

testCase = int(input())

for tc in range(testCase):
    N, M = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]

    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]
    answer = 0
    K = N + 1

    for k in range(K, 0, -1):
        cost = k * k + (k - 1) * (k - 1)
        for y in range(N):
            for x in range(N):
                bfs(y, x, k, cost)
        if answer != 0:
            break

    print("#{} {}".format(tc+1, answer))

---

두 번째 접근

위에서 불필요한 곳까지 접근하여 BFS를 진행했기 때문에 시간이 많이 소요되었다.

이제 집의 위치를 기억한 다음 NxN를 탐색하면서 각각의 위치에서 집 까지의 거리를 구하고, 거리가 K이하인 집만 카운트한다. 이 방법으로 해결했을 때 10배 정도 시간이 감소되었다.

 

두 번째 구현

- 집의 위치를 houses에 기록한다.

- solve 함수에서 NxN 크기의 2차원 리스트를 탐색하여 y, x를 기준으로 집들의 거리를 구한다.

- 거리가 k 미만일 때 집의 개수를 카운트하고

- 집의 개수 x M이 운영비용보다 크거나 같을 때 최댓값 비교를 한다.

- 이제 해당 k에서 answer가 0이 아닐 때는 반환하도록 한다.

testCase = int(input())

def solve():
    answer = 0
    K = N + 1

    for k in range(K, 0, -1):
        cost = k * k + (k - 1) * (k - 1)
        for y in range(N):
            for x in range(N):
                count = 0
                for hy, hx in houses:
                    dist = abs(hy - y) + abs(hx - x)
                    if dist < k:
                        count += 1
                if count * M >= cost:
                    answer = max(answer, count)
        if answer != 0:
            return answer
    return answer

for tc in range(testCase):
    N, M = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]
    houses = []
    for i in range(N):
        for j in range(N):
            if board[i][j]:
                houses.append((i, j))

    answer = solve()
    print("#{} {}".format(tc+1, answer))