[Java] SWEA 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 배열이 주어진다.

---

일단 이해하자🤔

• 스터디 조장님의 로직을 참고했다. N x N 배열을 벗어날때 if문을 사용해서 예외 처리를 해준다면 코드가 복잡해질 것 같아 N x N 배열 주위를 N x N 배열 8개가 둘러싸는 방식을 사용했다. 즉, 3N x 3N 배열을 선언하여 가운데 배열이 아니라면 값을 안 넣는 것이다. 그럼 자동으로 나머지 배열에는 0이 들어가는 것이다.
• +형태와 x형태 중 큰 값을 구해야 하는데, +형은 (가로 줄 + 세로 줄 - 기준 좌표), x형은 (\ 대각선 + / 대각선 - 기준 좌표)와 같은 방식으로 구하고 값 비교는 if문 대신 하늬가 알려준 Math.max(max, sum)을 사용했다. 파리 잡기 성공!🪰
• 알고리즘 문제를 풀때마다 코드를 깔끔하게 짜는 방법에 관심이 생긴다. Math.max(max, sum)과 같이 쓸데없는 코드를 조금이라도 줄여보자.

---

👀 풀이

import java.util.Scanner;

/**
 *
 * @author 김유나
 *
 * SWEA 12712 파리퇴치
 * 1. N x N 크기의 파리 개체 수 배열 주위를 N x N 배열로 감싼다.
 * -> M은 2 이상 N 이하이기 때문에 N x N 크기면 됨
 * 2. +형 / x형으로 분사될 경우 sum 값 계산
 * 2-(1) +형으로 분사될 경우 : 가로 줄 + 세로 줄 - 가운데 값
 * 2-(2) x형으로 분사될 경우 : \ 대각선 + / 대각선 - 가운데 값
 */

class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();

        for(int test_case = 1; test_case <= T; test_case++)
        {
            int N = sc.nextInt();
            int M = sc.nextInt();
            int max = 0; // test_case별 구할 max 값 초기화

            // N x N 배열과 그 주위를 감쌀 배열 3N x 3N 선언
            int arr[][] = new int[3 * N][3 * N];


            // 파리 개체 수 arr[N][N] ~ arr[2N - 1][2N-1] 배열에 넣기
            for (int i = N; i < 2 * N; i++) {
                for (int j = N; j < 2 * N; j++) {
                    arr[i][j] = sc.nextInt();
                }
            }


            // 파리 잡기 시작
            for (int i = N; i < 2 * N; i++) {
                for (int j = N; j < 2 * N; j++) {
                    int sum = 0; // sum 값은 기준 좌표가 바뀔때마다 초기화

                    // 1. +형으로 분사될 때 : 가로 한 줄 더하고 세로 한 줄 더한 뒤, 가운데 값 빼기

                    // 가로, 세로 한 줄 더하기
                    for (int k = -M + 1; k <= M - 1; k++) {
                        sum += arr[i][j + k];
                        sum += arr[i + k][j];
                    }

                    sum -= arr[i][j];

                    // max보다 큰지 비교
                    max = Math.max(max, sum);

                    // 형태가 바꼈으므로 sum 초기화
                    sum = 0;

                    // 2. x형으로 분사될 때 : \ 대각선 더하고 / 대각선 더한 뒤, 가운데 값 빼기

                    // \ 대각선, / 대각선 한 줄 더하기
                    for (int k = -M + 1; k <= M - 1; k++) {
                        sum += arr[i + k][j + k];
                        sum += arr[i - k][j + k];
                    }

                    sum -= arr[i][j];

                    // max보다 큰지 비교
                    max = Math.max(max, sum);
                }
            }

            System.out.println("#" + test_case + " " + max);
        }
    }
}