[SWEA] 2117. 홈 방범 서비스(Python)

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

SW Expert Academy

어렵지 않은 문제이나, 범위 설정하는데 꽤나 애를 먹었다ㅠㅠ

# 1시간 10분 소요

두 가지 방법으로 풀어봤다. 

첫 번째 방법은, 마름모의 모양을 BFS로 그리는 것이다.

• 먼저, 지름의 크기 K에 따라 값의 리스트를 미리 만들어놓는다.
• 맵 내의 모든 위치에서 bfs를 돌리며 중심으로부터 크기가 N+1이 될 때까지 마름모 내에 있는 집의 갯수를 구한다.
• 마름모의 지름이 1 커질 때마다 큐에 든 갯수만큼만 for문으로 검사를 해주며 다음 크기와 구분해준다.
• 이 때 손해를 보지 않는 한 가장 많은 집을 서비스한다고 했으니, 보안회사의 이익이 0 이상이면 최댓값을 갱신 가능 여부를 확인하고 갱신해준다.

 

파이썬 코드는 다음과 같다.

---

from collections import deque

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)
KLst = [k*k+(k-1)*(k-1) for k in range(26)]     # K의 값 리스트 미리 구해놓기

def bfs(sr, sc):
    global maxCnt
    visited = [[0] * N for _ in range(N)]
    visited[sr][sc] = 1
    Q = deque([(sr, sc)])

    home = A[sr][sc]
    dis = 1
    # 1 크기일 때도 검사
    if home * M - KLst[dis] >= 0:
        maxCnt = max(home, maxCnt)
    while dis < N+2:
        qlen = len(Q)
        for _ in range(qlen):
            r, c = Q.popleft()
            for d in range(4):
                nr = r + dr[d]
                nc = c + dc[d]
                if not (0 <= nr < N and 0 <= nc < N):
                    continue
                if not visited[nr][nc]:
                    visited[nr][nc] = 1
                    Q.append((nr, nc))
                    if A[nr][nc]:       # 집이 있는 경우
                        home += 1
        # 보안회사의 이익이 0 이상이면 최댓값 갱신
        if home*M - KLst[dis+1] >= 0:
            maxCnt = max(home, maxCnt)
        dis += 1


# main
T = int(input())
for tc in range(T):
    N, M = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(N)]

    maxCnt = 0
    for i in range(N):
        for j in range(N):
            bfs(i, j)       # 모든 위치에서 검사
    print("#{} {}".format(tc+1, maxCnt))

• 시간 : 771ms / 메모리 : 63,436 kb

---

다음으로 두 번째 방법은

• 집의 위치를 리스트에 담아놓고, 
• 지름 k의 크기별로 매 위치마다 집의 위치 리스트의 값들과 위치 좌표를 절대값의 합으로 비교하여 k 보다 작다면 마름모 범위 내이므로 집의 갯수를 늘려준다.
• 집 검사가 끝나면 보안회사의 이익을 확인해 0 이상이라면 최댓값을 갱신해준다.

한마디로, 4중 for문으로 풀었다. 코드로 이해하면 쉬울 것이다.

---

from collections import deque

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)
KLst = [k*k+(k-1)*(k-1) for k in range(26)]     # K의 값 리스트 미리 구해놓기

# main
T = int(input())
for tc in range(T):
    N, M = map(int, input().split())
    A = []
    homeLst = []
    for i in range(N):
        A.append(list(map(int, input().split())))
        for j in range(N):
            if A[i][j]:
                homeLst.append((i, j))
    # print(homeLst)
    maxCnt = 0
    for k in range(1, N+2):
        for i in range(N):
            for j in range(N):
                home = 0
                for r, c in homeLst:
                    if abs(i-r) + abs(j-c) < k:
                        home += 1
                if home * M - KLst[k] >= 0:
                    maxCnt = max(home, maxCnt)

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

• 시간 : 566ms / 메모리 : 61,092 kb

---

• 고찰 : 시간 메모리가 압도적으로 적게 소요된다. 어렵게 풀지 말고 쉽게 풀 수 있는 건 쉽게 풀자!