[Java] 백준 14500 : 테트로미노

🔗 문제 내용

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

14500번: 테트로미노

🌱 문제 풀이 방법

​
나올 수 있는 모든 테트로미노를 구해서 최댓값을 찾는 방식으로 풀었다.
나올 수 있는 모든 테트로미노는 아래와 같다. 19가지 모양의 도형이 나온다.

(0,0)부터 (N-1,M-1)까지 19개의 테트로미노를 대입해본다.

테트로미노가 배열의 범위를 초과하지 않는다면, 최댓값을 구했다.

​

🤔 공부가 필요한 부분

​
지금은 테트로미노(4-오미노)지만, 펜토미노(5-오미노)와 같이 나올 수 있는 도형의 경우의 수가 더 다양해진다면 아래 코드처럼 모든 도형을 확인하기에는 한계가 있을 수 있다.  

다른 풀이를 고민해야 한다.
​

💻 코드

​

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

public class Main_14500_테트로미노 {

	// 나올 수 있는 19개의 테트로미노의 좌표
	static int[][][] tetromino = { { { 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 }, { 1, 0 }, { 2, 0 }, { 2, 1 } }, { { 2, 0 }, { 2, 1 }, { 1, 1 }, { 0, 1 } },
			{ { 0, 0 }, { 0, 1 }, { 0, 2 }, { 1, 0 } }, { { 0, 0 }, { 0, 1 }, { 0, 2 }, { 1, 2 } },
			{ { 0, 0 }, { 0, 1 }, { 1, 0 }, { 2, 0 } }, { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 2, 1 } },
			{ { 0, 0 }, { 1, 0 }, { 1, 1 }, { 1, 2 } }, { { 1, 0 }, { 1, 1 }, { 1, 2 }, { 0, 2 } },
			{ { 0, 0 }, { 1, 0 }, { 1, 1 }, { 2, 1 } }, { { 0, 1 }, { 1, 1 }, { 1, 0 }, { 2, 0 } },
			{ { 0, 0 }, { 0, 1 }, { 1, 1 }, { 1, 2 } }, { { 1, 0 }, { 1, 1 }, { 0, 1 }, { 0, 2 } },
			{ { 0, 0 }, { 0, 1 }, { 0, 2 }, { 1, 1 } }, { { 1, 0 }, { 1, 1 }, { 1, 2 }, { 0, 1 } },
			{ { 0, 0 }, { 1, 0 }, { 2, 0 }, { 1, 1 } }, { { 1, 0 }, { 0, 1 }, { 1, 1 }, { 2, 1 } } };
	static int[][] map; // 지도 정보
	static int N, M, max;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		max = 0;
		N = Integer.parseInt(st.nextToken()); // 세로
		M = Integer.parseInt(st.nextToken()); // 가로
		map = new int[N][M]; // 종이에 쓰여 있는 수 정보를 담은 배열

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

		for (int r = 0; r < N; r++) {
			for (int c = 0; c < M; c++) {
				calculate(r, c); // (0,0)부터 (N-1,M-1)까지 테트로미노 값 계산
			}
		}
		System.out.println(max);
	}

	static void calculate(int r, int c) {
		for (int i = 0; i < 19; i++) {
			int sum = 0; // 테트로미노가 놓인 칸에 쓰여 있는 수들의 합
			boolean flag = true;
			for (int j = 0; j < 4; j++) {
				if (flag) {
					int newR = r + tetromino[i][j][0];
					int newC = c + tetromino[i][j][1];
					if (chk(newR, newC)) { // 테트로미노가 놓인 칸이 종이 범위인 경우 합 계산
						sum += map[newR][newC];
					} else {
						flag = false; // 테트로미노가 놓인 칸이 종이 범위를 초과하는 경우
					}
				}
			}
			if (flag) {
				max = Math.max(max, sum); // 테트로미노가 놓인 칸이 종이 범위를 안 넘은 경우 최댓값인지 확인
			}
		}
	}

	// 종이 범위를 넘는지 확인
	static boolean chk(int r, int c) {
		if (r >= N || r < 0 || c >= M || c < 0) {
			return false;
		}
		return true;
	}
}