[JAVA] SW Expert Academy #2001 파리 퇴치 문제 풀이 | ArrayList | 완전 탐색

 

---

SWEA #2001 파리 퇴치

🔒 문제 설명

N x N 배열 안의 숫자는 해당 영역에 존재하는 파리의 개수를 의미한다. 아래는 N=5의 예이다.

 

M x M 크기의 파리채를 한 번 내리쳐 최대한 많은 파리를 죽이고자 한다. 죽은 파리의 개수를 구하라!
예를 들어 M=2 일 경우 위 예제의 정답은 49마리가 된다.
 

[제약 사항]

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

⌨️ 입력

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

🖥️ 출력

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다.
(t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

 

---

🗝️Solution

나는 해당 문제를 '완전 탐색'으로 풀었다. 단순히 말하자면 4중 for문을 사용해서 코드를 구현했다..!

for문을 3중 이상 사용하는 것을 선호하지 않지만 다른 방법은 떠오르지 않는다. 

우선 2차원 배열 Field에 모든 영역의 파리 개수를 입력받아서 저장하고,

m x m의 파리채가 필드 위를 처음부터 끝까지 순회하면서 max값을 갱신해 나가는 방식이다.

코드는 아래와 같다.

 

import java.util.ArrayList;
import java.util.Scanner;
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; //최대 파리 개수

            // Field = N x N 영역
            ArrayList<ArrayList<Integer>> Field = new ArrayList<>();

            // [1] 입력값을 2차원 배열 Field에 담기
            for(int i = 0; i < N; i++){
                ArrayList<Integer> row = new ArrayList<>();
                for(int j = 0; j < N; j++){
                    int n = sc.nextInt();
                    row.add(n);
                }
                Field.add(row);
            }

            //[2] 파리채를 하나하나 대보며 최댓값 구하기
            for(int i = 0; i < N - M + 1 ; i++){
                for(int j = 0; j < N - M + 1 ; j++){

                    int sum = 0; //파리 개수
                    for(int k = i; k < i+M; k++){
                        for(int l = j; l < j+M; l++){
                            sum+=Field.get(k).get(l);
                        }
                    }
                    if(sum>max) max = sum;
                }
            }
            System.out.println("#"+test_case+" "+max);
        }
    }
}