SWEA 홈방범서비스 python (파이썬)

단순한 BFS 문제였다.

처음에 생각을 잘못한 부분은 → NxN 에서 가장 큰 마른모는 N일때 발생한다고 생각했는데,

N+1 일때 발생한다는 것이 key 였다. (그것때문에 49/50 개 pass 였다. 😿)

실제로 예시의 사진을 보면, 3x3 배열이 쏙 들어가는건 마름모가 k=4 일때임을 알 수 있다!

앞으로 이런 디테일에 더 주의해서 문제를 풀어야 겠다.

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


# BFS 함수를 입력
def BFS(i, j, k):
    global house
    q = deque()
    q.append((i, j))
    cnt = 1
    if homes[i][j] == 1:
        house += 1

    while cnt < k:
        for _ in range(len(q)):
            si, sj = q.popleft()
            for d in range(4):
                ni, nj = si + dx[d], sj + dy[d]
                if 0 <= ni < N and 0 <= nj < N:
                    if visited[ni][nj] == 0:
                        visited[ni][nj] = 1
                        q.append((ni, nj))
                        if homes[ni][nj] == 1:
                            house += 1
        cnt += 1


# 운영비용을 미리 계산한 list를 만들어 둔다.
running = [((k ** 2) + (k - 1) ** 2) for k in range(22)]
# 반복문을 통해서 돌릴 때에는, append 대신 한줄로 간략하게 표현 잊지 말자
T = int(input())

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

    max_V = 0
    # K = 1부터 돌면서 이익이 나는지 검사한다.
    for k in range(1, N + 2):
        for i in range(N):
            for j in range(N):
                visited = [[0] * N for _ in range(N)]
                visited[i][j] = 1
                house = 0
                BFS(i, j, k)

                rate = house * M
                if rate - running[k] >= 0:
                    max_V = max(house, max_V)
    print(f"#{tc} {max_V}")

Uploaded by N2T