[SW Expert Academy] 12712. 파리퇴치3

12712. 파리퇴치3

---

문제)

 

N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개체 수를 의미한다.

아래는 N=5 의 예이다.

 

 

 

파리 킬러 스프레이를 한 번만 뿌려 최대한 많은 파리를 잡으려고 한다. 스프레이의 노즐이 + 형태로 되어있어, 스프레이는 + 혹은 x 형태로 분사된다. 스프레이를 M의 세기로 분사하면 노즐의 중심이 향한 칸부터 각 방향으로 M칸의 파리를 잡을 수 있다.

다음은 M=3 세기로 스프레이르 분사한 경우 파리가 퇴치되는 칸의 예로, +또는 x 중 하나로 분사된다. 뿌려진 일부가 영역을 벗어나도 상관없다.

 

 

 

한 번에 잡을 수 있는 최대 파리수를 출력하라.

 

[제약 사항]

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

[입력]

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에 N 과 M 이 주어지고,
다음 N 줄에 걸쳐 N x N 배열이 주어진다.

 

 

 

 

풀이)

T = int(input())
for _ in range(T):
 
    n, m = map(int, input().split())
    li = [list(map(int, input().split())) for i in range(n)]
 
    di = [-1, 1, 0, 0]
    dj = [0, 0, -1, 1]
 
    ti = [-1, 1, -1, 1]
    tj = [-1, 1, 1, -1]
 
    total = 0
    answer = 0
    for i in range(n):
        for j in range(n):
            cnt1 = li[i][j] # +모양 분사
            cnt2 = li[i][j] # x모양 분사
            for k in range(4): # 방향
                for l in range(1, m): # 분사 세기
                    a = i + di[k] * l
                    b = j + dj[k] * l
 
                    c = i + ti[k] * l
                    d = j + tj[k] * l
 
                    # 인덱스 범위 체크
                    if -1 < a < n and -1 < b < n:
                        cnt1 += li[a][b]
 
                    if -1 < c < n and -1 < d < n:
                        cnt2 += li[c][d]
 
            total = max(cnt1, cnt2)
            if answer < total: # 정답 갱신
                answer = total
 
    print(f"#{_ + 1}", answer)

---

문제 출처 : https://swexpertacademy.com/main/main.do

SW Expert Academy

※ SW Expert 아카데미는 원칙적으로 문제를 무단 복제하는 것을 금지합니다.

학습용으로 문제를 가져왔으나, 문제가 될 시 수정 및 삭제하겠습니다.