알고리즘/백준 알고리즘(JAVA)
JAVA)14500번 테트로미노 - 브루트 포스
starmk95
2020. 8. 3. 19:16
import java.util.*;
public class Main {
static int[][] value;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 세로크기(행)
int M = sc.nextInt(); // 가로크기(열)
value = new int[N][M];
// 각 칸의 값 받아서 2차월 배열에 저장
for (int i=0;i<N;i++) {
for (int j=0;j<M;j++) {
value[i][j] = sc.nextInt();
}
}
// 브루트 포스
// 테트로미노가 붙는 모든 경우의 수를 고려하여 최대값 도출
// 5가지 모형의 테트로미노는 모두 19가지의 경우로 붙을 수 있다. (회전, 대칭 포함)
// 경우의 수 : 어떤 테트로미노를 놓을지(19가지) * 어디에 놓을지(N*M가지) = 19*N*M가지
// N과 M의 최대값은 500이므로 가장 많은 경우의 수는 19*500*500 = 4750000
// 1억 가지의 경우의 수를 고려하는 것이(1가지 고려에 O(1)이라면) 1초가 걸린다는 것을 생각하면
// 그렇게 많은 경우가 아니므로 브루트 포스 이용 가능.
int ans = 0;
for (int i=0;i<N;i++) {
for (int j=0;j<M;j++) { // 모든 칸에 대해 검사 수행
if (j+3 < M) {
int temp = value[i][j] + value[i][j+1] + value[i][j+2] + value[i][j+3];
if (ans < temp) ans = temp;
}
if (i+3 < N) {
int temp = value[i][j] + value[i+1][j] + value[i+2][j] + value[i+3][j];
if (ans < temp) ans = temp;
}
if (i+1 < N && j+2 < M) {
int temp = value[i][j] + value[i+1][j] + value[i+1][j+1] + value[i+1][j+2];
if (ans < temp) ans = temp;
}
if (i+2 < N && j+1 < M) {
int temp = value[i][j] + value[i][j+1] + value[i+1][j] + value[i+2][j];
if (ans < temp) ans = temp;
}
if (i+1 < N && j+2 < M) {
int temp = value[i][j] + value[i][j+1] + value[i][j+2] + value[i+1][j+2];
if (ans < temp) ans = temp;
}
if (i+2 < N && j-1 >= 0) {
int temp = value[i][j] + value[i+1][j] + value[i+2][j] + value[i+2][j-1];
if (ans < temp) ans = temp;
}
if (i-1 >= 0 && j+2 < M) {
int temp = value[i][j] + value[i][j+1] + value[i][j+2] + value[i-1][j+2];
if (ans < temp) ans = temp;
}
if (i+2 < N && j+1 < M) {
int temp = value[i][j] + value[i+1][j] + value[i+2][j] + value[i+2][j+1];
if (ans < temp) ans = temp;
}
if (i+1 < N && j+2 < M) {
int temp = value[i][j] + value[i][j+1] + value[i][j+2] + value[i+1][j];
if (ans < temp) ans = temp;
}
if (i+2 < N && j+1 < M) {
int temp = value[i][j] + value[i][j+1] + value[i+1][j+1] + value[i+2][j+1];
if (ans < temp) ans = temp;
}
if (i+1 < N && j+1 < M) {
int temp = value[i][j] + value[i][j+1] + value[i+1][j] + value[i+1][j+1];
if (ans < temp) ans = temp;
}
if (i-1 >= 0 && j+2 < M) {
int temp = value[i][j] + value[i][j+1] + value[i-1][j+1] + value[i-1][j+2];
if (ans < temp) ans = temp;
}
if (i+2 < N && j+1 < M) {
int temp = value[i][j] + value[i+1][j] + value[i+1][j+1] + value[i+2][j+1];
if (ans < temp) ans = temp;
}
if (i+1 < N && j+2 < M) {
int temp = value[i][j] + value[i][j+1] + value[i+1][j+1] + value[i+1][j+2];
if (ans < temp) ans = temp;
}
if (i+2 < N && j-1 >= 0) {
int temp = value[i][j] + value[i+1][j] + value[i+1][j-1] + value[i+2][j-1];
if (ans < temp) ans = temp;
}
if (j+2 < M) {
int temp = value[i][j] + value[i][j+1] + value[i][j+2];
if (i-1 >= 0) {
int temp2 = temp + value[i-1][j+1];
if (ans < temp2) ans = temp2;
}
if (i+1 < N) {
int temp2 = temp + value[i+1][j+1];
if (ans < temp2) ans = temp2;
}
}
if (i+2 < N) {
int temp = value[i][j] + value[i+1][j] + value[i+2][j];
if (j+1 < M) {
int temp2 = temp + value[i+1][j+1];
if (ans < temp2) ans = temp2;
}
if (j-1 >= 0) {
int temp2 = temp + value[i+1][j-1];
if (ans < temp2) ans = temp2;
}
}
}
}
System.out.println(ans);
}
}