SWExpert Academy: 2001. 파리 퇴치

태그 잊지 않고 붙이세요
#sw_expert_academy #Implementation #D2
문제 링크

제한사항

[제약 사항]

1. N 은 5 이상 15 이하이다.
2. M은 2 이상 N 이하이다.
3. 각 영역의 파리 갯수는 30 이하 이다.

문제 정리

파리가 가장 많이 죽는 위치를 선택하라.

접근 방법

파리가 가장 많이 죽는 위치를 구해야한다.
2차원 배열 모든 점을 시작점으로 삼고 DFS를 통해 모든 값을 일일이 계산하는 방법을 사용했다.
(row, col) 지점에서 대각선, 오른쪽, 아래 방향으로 DFS 진행하여 누적합을 구했다.
시간복잡도는 N^2 * M^2
무식한 방법이지만 제약 사항을 먼저 확인했다면 해당 시간복잡도로 충분히 통과 가능함을 알 수 있다.

복잡도

시간복잡도: O(N^2 * M^2)
공간복잡도: O(N^2)

코드

T = int(input())

def dfs(position, depth: int, max_depth: int, area: list, visited: list) -> int:
    sum = area[position[0]][position[1]]
    if depth >= max_depth:
        return sum

    directions = [(1, 1), (0, 1), (1, 0)]
    for dir in directions:
        next_position = (position[0] + dir[0], position[1] + dir[1])
        if next_position[0] not in range(len(area)) or next_position[1] not in range(len(area[0])) or visited[next_position[0]][next_position[1]]:
            continue
        visited[next_position[0]][next_position[1]] = True
        sum = sum + dfs(next_position, depth + 1, max_depth, area, visited)

    return sum

for test_case in range(1, T + 1):
    n, m = map(int, input().split())
    area = [ list(map(int, input().split())) for _ in range(n) ]

    answer = 0
    for row in range(len(area)):
        for col in range(len(area[0])):
            visited = [[False] * n for _ in range(n)]
            visited[row][col] = True
            sum = dfs((row, col), 1, m, area, visited)
            answer = max(answer, sum)
    print(f"#{test_case} {answer}")