[swea] [모의 sw 역량테스트] 2117. 홈 방범 서비스 python

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu&categoryId=AV5V61LqAf8DFAWu&categoryType=CODE&problemTitle=%ED%99%88+%EB%B0%A9%EB%B2%94&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

🔥 작성코드

# bfs
def sol(si, sj, k):
    global result

    q = []
    q.append([si, sj])
    vst = [[0 for _ in range(N)] for _ in range(N)]
    vst[si][sj] = 1

    # 방범 서비스 받은 home 수
    cnt = 0

    # 시작지점이 집이면 1 추가하고 시작
    if arr[si][sj] == 1:
        cnt += 1
    while q:
        si, sj = q.pop(0)
        n = vst[si][sj]
        # k만큼 이동한 모양 완. 성.
        if vst[si][sj] >= k:
            if cost[k] <= cnt*M and result < cnt:
                result = cnt
            return
        # 4방향으로 탐색
        for d in range(4):
            ni = si + di[d]
            nj = sj + dj[d]
            # 갈 수 있는 곳이면 go
            if 0 <= ni < N and 0 <= nj < N and vst[ni][nj] == 0 and arr[ni][nj] == 0:
                vst[ni][nj] = n + 1
                q.append([ni, nj])
            # 갈 수 있는 집이면 cnt 증가
            elif 0 <= ni < N and 0 <= nj < N and vst[ni][nj] == 0 and arr[ni][nj] == 1:
                vst[ni][nj] = n + 1
                q.append([ni, nj])
                cnt += 1


T = int(input())

di = [1, -1, 0, 0]
dj = [0, 0, -1, 1]

# k에 따른 방범 비용 저장
cost = [n**2 for n in range(22)]
for i in range(1, 22)[::-1]:
    cost[i] += cost[i-1]

for test_case in range(1, T+1):
    N, M = map(int, input().split())

    arr = [list(map(int, input().split())) for _ in range(N)]

    # 도시의 총 집 수 tot
    tot = 0
    for i in range(N):
        tot += arr[i].count(1)

    # 도시 전체 방범 시 모든 집 방범 서비스 가능
    if cost[N+1] <= tot*M:
        result = tot

    # 도시 전체 방범할 비용 없으면 탐색
    else:
        result = 0
        flag = 0
        for i in range(N):
            if flag == 1:
                break
            for j in range(N):
                if flag == 1:
                    break
                for k in range(1, N+2):
                    if result >= tot:
                        flag = 1
                        break
                    elif cost[k] > result:
                        sol(i, j, k)

    print(f'#{test_case} {result}')

 

⭕ 해설

1. k에 따라 bfs범위를 조정하며 탐색했습니다.
2. tc를 돌기전에 미리 k만큼 서비스를 할 때의 운영비용을 구해놨습니다.
   • dp를 이용하여 계산 
3. k가 N+1이라면 도시의 모든 집을 방문할 수 있습니다.
   • 만약 이 때 드는 비용이 수익보다 크거나 같다면 손해가 아니므로 집의 수를 출력합니다.
4. 위의 방법에서 손해를 본다면 모든 위치에서 k를 1부터 N+1까지 bfs탐색합니다.
   • 이 부분을 미리 계산했다면 범위를 지정해 시간을 줄였을 수 있었겠네요.
5. 모양대로 탐색을 하고나면 거기에 포함된 집에 서비스를 제공할 수 있는지 확인하고 결과를 갱신합니다. 

 

 

🔥 새로 작성한 코드 (훨씬 빠름)

def sol(si, sj):
    global result, flag

    # 각 집까지 걸리는 거리를 계산, 해당 거리에 있는 집의 수 저장
    cnt = [0] * (N+1)
    for ei, ej in home:
        dist = abs(ei - si) + abs(ej - sj)
        if dist <= N:
            cnt[dist] += 1

    # k에 대해 손해발생하지 않는 선에서 최대 집 개수 갱신
    for i in range(len(cnt)):
        if cost[i+1] <= M*sum(cnt[:i+1]) and result < sum(cnt[:i+1]):
            result = sum(cnt[:i+1])
    if result >= tot:
        flag = 1


T = int(input())

di = [1, -1, 0, 0]
dj = [0, 0, -1, 1]

cost = [n**2 for n in range(22)]
for i in range(1, 22)[::-1]:
    cost[i] += cost[i-1]

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

    tot = 0
    home = []
    for i in range(N):
        for j in range(N):
            if arr[i][j] == 1:
                tot +=1
                home.append([i, j])

    result = 0
    flag = 0
    if cost[N+1] <= M*tot:
        result = tot
    else:
        for i in range(N):
            if flag == 1:
                break
            for j in range(N):
                sol(i, j)

    print(f'#{test_case} {result}')

⭕ 해설

1. 위와 마찬가지로 k에 따른 운영비용을 미리 구해두었습니다.
2. k가 N+1일 때는 모든 집을 방문할 수 있으며, 운영 비용만 가능하다면 이것이 답입니다.
3. 위의 방법에서 손해를 본다면 k는 N+1이 될 수 없는 것이므로 각 지점마다 k는 1부터 N까지 확인합니다.
   • 각 지점에서 집까지의 거리를 계산합니다.
   • cnt에 거리마다 집의 개수를 저장합니다. (cnt[1] == 해당 지점에서 거리가 1인 집의 수)
4. k=1 부터 N까지 손해보지 않으면서 가장 많은 집을 서비스하는 경우를 찾습니다.