[Java] BOJ14500_테트로미노

www.acmicpc.net/problem/14500

14500번: 테트로미노

---

각 칸에 가능한 테트로미노의 모양을 다 놓아보고 최댓값을 찾는 문제이다.

i 행 j 열이 노란색칸일 때 가능한 테트로미노 모양은 위와 같이 19가지가 나오며 이 모양들 중 배열의 범위를 벗어나지 않는 모양들을 놓아보고 각 칸의 합을 구해 최댓값을 구한다.

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	
	static int N, M;
	static int[][] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N][M];
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < M; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int max = Integer.MIN_VALUE;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				max = Math.max(max, setTetro(i, j));
			}
		}
		
		System.out.println(max);
		
	}
	private static int setTetro(int r, int c) {
		int max = Integer.MIN_VALUE;
		if(r + 3 < N) max = Math.max(max, arr[r][c]+arr[r+1][c]+arr[r+2][c]+arr[r+3][c]);  //세로 쭉
		if(c + 3 < M) max = Math.max(max, arr[r][c]+arr[r][c+1]+arr[r][c+2]+arr[r][c+3]);  //가로 쭉
		if(r + 1 < N && c + 1 < M) max = Math.max(max, arr[r][c]+arr[r+1][c]+arr[r][c+1]+arr[r+1][c+1]); //사각형
		if(r + 2 < N && c - 1 >= 0) max = Math.max(max, arr[r][c]+arr[r+1][c]+arr[r+1][c-1]+arr[r+2][c-1]);
		if(r + 2 < N && c + 1 < M) max = Math.max(max, arr[r][c]+arr[r+1][c]+arr[r+1][c+1]+arr[r+2][c+1]);
		if(r + 1 < N && c - 2 >= 0) max = Math.max(max, arr[r][c]+arr[r][c-1]+arr[r+1][c-1]+arr[r+1][c-2]);
		if(r + 1 < N && c + 2 < M) max = Math.max(max, arr[r][c]+arr[r][c+1]+arr[r+1][c+1]+arr[r+1][c+2]);  //꺽인 모양
		if(r + 1 < N && r - 1 >= 0 && c + 1 < M) max = Math.max(max, arr[r][c]+arr[r+1][c]+arr[r][c+1]+arr[r-1][c]);
		if(r + 1 < N && r - 1 >= 0 && c - 1 >= 0) max = Math.max(max, arr[r][c]+arr[r+1][c]+arr[r][c-1]+arr[r-1][c]);
		if(c + 1 < M && c - 1 >= 0 && r + 1 < N) max = Math.max(max, arr[r][c]+arr[r+1][c]+arr[r][c+1]+arr[r][c-1]);
		if(c + 1 < M && c - 1 >= 0 && r - 1 >= 0) max = Math.max(max, arr[r][c]+arr[r][c-1]+arr[r][c+1]+arr[r-1][c]); // +
		if(r + 1 < N && c + 2 < M) {
			max = Math.max(max, arr[r][c]+arr[r][c+1]+arr[r][c+2]+arr[r+1][c+2]);
			max = Math.max(max, arr[r][c]+arr[r+1][c]+arr[r+1][c+1]+arr[r+1][c+2]);
		}
		if(r + 1 < N && c - 2 >= 0) {
			max = Math.max(max, arr[r][c]+arr[r][c-1]+arr[r][c-2]+arr[r+1][c-2]);
			max = Math.max(max, arr[r][c]+arr[r+1][c]+arr[r+1][c-1]+arr[r+1][c-2]);
		}
		if(r + 2 < N && c + 1 < M) {
			max = Math.max(max, arr[r][c]+arr[r][c+1]+arr[r+1][c+1]+arr[r+2][c+1]);
			max = Math.max(max, arr[r][c]+arr[r+1][c]+arr[r+2][c]+arr[r+2][c+1]);
		}
		if(r + 2 < N && c - 1 >= 0) {
			max = Math.max(max, arr[r][c]+arr[r][c-1]+arr[r+1][c-1]+arr[r+2][c-1]);
			max = Math.max(max, arr[r][c]+arr[r+1][c]+arr[r+2][c]+arr[r+2][c-1]);
		}
		
		
		return max;
	}
}