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

link 🔗 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu 

SW Expert Academy

 

 

from collections import deque

def bfs(y, x):
    global Max, M
    check = [[0]*N for _ in range(N)]
    q = deque()
    q.append((y, x)) # y, x
    check[y][x] = 1
    K = 0 # 제공 범위
    home = 0 # 방범 서비스 받는 집의 개수
    if arr[y][x] == 1: # 시작 지점에 집이 있으면 더해주기
        home += 1
    while q:
        ny, nx = q.popleft()
        if check[ny][nx] != K:
            K = check[ny][nx]
            cost = K * K + (K - 1) * (K - 1)
            if M * home >= cost:
                if Max < home:
                    Max = home

        direct = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상 하 좌 우
        for idx in range(4):
            dy = direct[idx][0]+ny
            dx = direct[idx][1]+nx
            if 0 <= dy < N and 0 <= dx < N:
                if check[dy][dx] > 0: continue # 이미 서비스 사용 중이면 X
                check[dy][dx] = K+1
                if arr[dy][dx] == 1:
                    home += 1
                q.append((dy, dx))
    return Max

t = int(input())

for tc in range(1, t+1):
    Max = -1e9
    N, M = map(int, input().split()) # 도시 크기 N, 집마다 지불 비용 M
    arr = [list(map(int, input().split())) for _ in range(N)]
    for y in range(N):
        for x in range(N):
                bfs(y, x)

    print(f'#{tc} {Max}')

 

✏️ 메모

• 보자마자 floodfill로 풀면 되겠다고 감이 와서 신났다!
• 하지만... 여전히 실수투성이...🥲
• 자잘한 부분 (시작점에 집이 있을 때만 home에 1을 더해줘야 한다든지)에서 실수가 많아서 한 번에 답을 내진 못했다
• 그래도 언젠간,,, 설계 한 번에 딱 하고 답도 한 번에 딱 나오는 날이 있지 않을까?!ㅋㅋㅋ
• 쉽게만 살아가면 재미없어 빙고,,,🥲🎵