[백준 14500] 테트로미노 - JAVA

문제

문제 정의

• 테트로미노는 회전, 대칭 가능
• $N * M$의 보드판에 테트로미노 하나를 적절히 놓았을 때
• 테트로미노가 놓인 칸에 쓰여있는 수들의 합의 최댓값 구하기

---

접근 방법

1. 테트로미노를 회전 시켰을 때 나올 수 있는 모든 모양 구하기

5가지의 테트로미노를 회전시켰을 때 나올 수 있는 모양은 다음과 같습니다.

---

2. 완전 탐색으로 최댓값 계산

• $N * M$ 그리드의 모든 칸 $(i, j)$를 순서대로 방문
• $(i, j)$에서 $19$가지 모양을 모두 대입해보면서 최댓값 갱신

---

getValue() 로직

• 현재의 테트로미노를 현재 좌표 기반으로 놓을 수 있다면 놓기
• 놓을 수 없다면 $-1$, 놓을 수 있다면 테트로미노를 놓은 값 반환

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static StringTokenizer st;
    static int[][][] tetrominos =
            {
                    {{0, 0}, {0, 1}, {0, 2}, {0, 3}}, {{0, 0}, {1, 0}, {2, 0}, {3, 0}},
                    {{0, 0}, {0, 1}, {1, 0}, {1, 1}},
                    {{0, 0}, {0, 1}, {-1, 1}, {1, 0}}, {{0, 0}, {0, 1}, {-1, 0}, {1, 1}}, {{0, 0}, {1, 0}, {0, -1}, {1, 1}}, {{0, 0}, {1, 0}, {0, 1}, {1, -1}},
                    {{0, 0}, {1, -1}, {1, 0}, {1, 1}}, {{0, -1}, {0, 0}, {0, 1}, {1, 0}}, {{-1, 0}, {0, 0}, {1, 0}, {0, 1}}, {{-1, 0}, {0, 0}, {1, 0}, {0, -1}},
                    {{0, 0}, {1, 0}, {2, 0}, {2, -1}}, {{0, 0}, {1, 0}, {2, 0}, {2, 1}}, {{0, 0}, {0, 1}, {0, 2}, {-1, 0}}, {{0, 0}, {0, 1}, {0, 2}, {1, 0}},
                    {{0, 0}, {1, 0}, {2, 0}, {0, -1}}, {{0, 0}, {1, 0}, {2, 0}, {0, 1}}, {{0, 0}, {0, 1}, {0, 2}, {1, 2}}, {{0, 0}, {0, 1}, {0, 2}, {-1, 2}}
            };
    static int answer = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                values[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                for (int[][] tetromino : tetrominos) {
                    answer = Math.max(answer, getValue(i, j, N, M, tetromino, values));
                }
            }
        }
        System.out.println(answer);
    }

    static int getValue(int y, int x, int N, int M, int[][] shape, int[][] values) {
        int value = 0;
        for (int i = 0; i < shape.length; i++) {
            int ny = y + shape[i][0];
            int nx = x + shape[i][1];
            if (ny < 0 || ny >= N || nx < 0 || nx >= M) return -1;
            value += values[ny][nx];
        }
        return value;
    }
}