[백준] 14500번 : 테트로미노- JAVA [자바]

https://www.acmicpc.net/problem/14500

---

브루트포스 알고리즘 문제이다.
각 테트로미노 모양을 회전이나 대칭을 하여 나올 수 있는 합 중 최대 합을 구하면 된다.

5 가지의 테트로미노 모양이 있다.

각 모양이 회전을 안한다고 했을 때, 현재 i 번째 줄 j 번째 칸일 때 나올 수 있는 모양과 범위를 정의해봤다.

1. 하늘색- 오른쪽으로 4칸인거

• arr[i][j] + arr[i][j+1] + arr[i][j+2] + arr[i][j+3] j+3 < N

2. 노란색 - 오른쪽으로 2칸 아래로 2칸

• arr[i][j] + arr[i][j+1] + arr[i+1][j] + arr[i+1][j+1] j+1 < N, i+1 < N

3. 주황색 - 아래로 3칸, 오른쪽으로 1칸

• arr[i][j] + arr[i+1][j] + arr[i+2][j] + arr[i+2][j+1] i+2 < N, j+1 < N

4. 초록색 - 아래로 2칸, 오른쪽으로 2칸, 아래로 1칸

• arr[i][j] + arr[i+1][j] + arr[i+1][j+1] + arr[i+1][j+1] i+2 < N, j+1 < N

5. 보라색 - 오른쪽으로 2칸 아래로 한칸 오른쪽으로 한칸

• arr[i][j] + arr[i][j+1] + arr[i+1][j+1] + arr[i][j+2] j+2 < N, i+1 < N

그 이후 회전과 대칭을 생각하면 총 19가지의 모양이 나온다.

각 모양의 범위를 나눠서 나올 수 있는 모양을 골라내고 나온 모양의 합이 더 크면 최대 합을 바꿔준다.

처음 앞에 3 개는 그냥 구하고 주황색부터 1번으로 번호를 매겨서 범위가 같은 것끼리 묶어서 풀었다. (7번은 초록색 첫번째 모양이다)

---

public class bj14500 {

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] split = br.readLine().split(" ");

        int N = Integer.parseInt(split[0]);
        int M = Integer.parseInt(split[1]);

        int[][] arr = new int[N][M];

        for (int i = 0; i < N; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(line[j]);
            }
        }

        int max = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 하늘색 오른쪽으로
                if (j + 3 < M) {
                    if (max < (arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i][j + 3]))
                        max = arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i][j + 3];
                }
                // 하늘색 아래쪽으로
                if (i + 3 < N) {
                    if (max < (arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 3][j]))
                        max = arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 3][j];
                }
                // 노란색
                if (i + 1 < N && j + 1 < M) {
                    if (max < (arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 1][j + 1]))
                        max = arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 1][j + 1];
                }
                // i + 2 < N, j + 1 < M 안에 범위
                if (i + 2 < N && j + 1 < M) {
                    // 1, 3, 4, 7, 14
                    max = Math.max(max, (arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 2][j + 1]));
                    max = Math.max(max, (arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 2][j]));
                    max = Math.max(max, (arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 2][j + 1]));
                    max = Math.max(max, (arr[i][j] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 2][j + 1]));
                    max = Math.max(max, (arr[i][j] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 2][j]));
                }
                // i + 2 < N, j > 0 안에 범위
                if (i + 2 < N && j > 0) {
                    // 2, 8, 16
                    max = Math.max(max, (arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 2][j - 1]));
                    max = Math.max(max, (arr[i][j] + arr[i + 1][j] + arr[i + 1][j - 1] + arr[i + 2][j - 1]));
                    max = Math.max(max, (arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 1][j - 1]));
                }
                // i + 1 < N, j + 2 < M
                if (i + 1 < N && j + 2 < M) {
                    // 5, 6, 9, 11
                    max = Math.max(max, (arr[i][j] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 1][j + 2]));
                    max = Math.max(max, (arr[i][j] + arr[i + 1][j] + arr[i][j + 1] + arr[i][j + 2]));
                    max = Math.max(max, (arr[i][j] + arr[i + 1][j + 2] + arr[i][j + 1] + arr[i][j + 2]));
                    max = Math.max(max, (arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 1][j + 2]));
                }
                // i > 0, j + 2 < M
                if (i > 0 && j + 2 < M) {
                    // 10, 12, 13, 15
                    max = Math.max(max, (arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i - 1][j + 2]));
                    max = Math.max(max, (arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i - 1][j + 2]));
                    max = Math.max(max, (arr[i][j] + arr[i][j + 1] + arr[i - 1][j + 1] + arr[i - 1][j + 2]));
                    max = Math.max(max, (arr[i][j] + arr[i][j + 1] + arr[i - 1][j + 1] + arr[i][j + 2]));
                    max = Math.max(max, (arr[i-1][j] + arr[i-1][j + 1] + arr[i - 1][j + 2] + arr[i][j + 1]));
                }
            }
        }

        bw.write(max + "\n");

        bw.flush();
        bw.close();
        br.close();
    }
}