[백준알고리즘] 브루트포스 - 14500번 테트로미노 문제

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

14500번: 테트로미노

 

테트로미노 도형은 총 5가지가 있는데 회전/반전까지 포함하자면 총 19개의 모양이 나올 수 있다.

NxM크기의 배열 내에 이 19개의 도형을 다 넣어보고 최대값을 찾으면 된다.

N,M은 최대 500이므로 최악의 경우라도 19 x 500 x 500 하면

(도형들이 배열안에 다 꽉차게 들어갈순 없으므로 이보다 실제로는 작은수겠지만)대략 4750000개가 된다.

1억에 비하면 작은 수이므로 시간제한 2초 내에 충분히 풀어볼 만 하다

따라서 2차원 배열 내에 19개 모양의 도형이 들어갈 수 있는 경우의 수를 다 넣어 풀도록 짰다.

단순무식하고 좋네요

 

package baekjoonWeek3;

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

public class Tetromino {    //백준 14500 테트로미노 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] board = new int[N][M];
        for (int i = 0; i < N; i++) {   //배열의 행
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int max = 0;
        int temp = 0 ;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                //가로 막대 모양
                if (j + 3 < M) {
                    temp = board[i][j] + board[i][j + 1] + board[i][j + 2] + board[i][j + 3];
                    if(temp > max) max = temp;
                }
                //세로 막대 모양
                if (i + 3 < N) {
                    temp = board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 3][j];
                    if(temp > max) max = temp;
                }
                //ㅁ자 막대 모양
                if (i + 1 < N && j + 1 < M) {
                    temp = board[i][j] + board[i + 1][j] + board[i][j + 1] + board[i + 1][j + 1];
                    if(temp > max) max = temp;
                }
                //ㄴ자 막대 모양 - 기본 ㄴ자
                if (i + 2 < N && j + 1 < M) {
                    temp = board[i][j] + board[i + 1][j] + board[i + 2][j] + board[i + 2][j + 1];
                    if(temp > max) max = temp;
                }
                //ㄴ자 막대 모양 - 좌우반전
                if (i + 2 < N && j + 1 < M) {
                    temp = board[i+2][j] + board[i][j+1] + board[i+1][j + 1] + board[i + 2][j + 1];
                    if(temp > max) max = temp;
                }
                //ㄴ자 막대 모양 - 상하반전
                if (i + 2 < N && j + 1 < M) {
                    temp = board[i][j] + board[i+1][j] + board[i+2][j] + board[i][j + 1];
                    if(temp > max) max = temp;
                }
                //ㄴ자 막대 모양 - 상하반전 & 좌우반전
                if (i + 2 < N && j + 1 < M) {
                    temp = board[i][j] + board[i][j+1] + board[i+1][j+1] + board[i+2][j + 1];
                    if(temp > max) max = temp;
                }
                //5. ㄴ자 막대 모양 - 오른쪽 회전 1번
                if (i + 1 < N && j + 2 < M) {
                    temp = board[i][j] + board[i+1][j] + board[i][j+1] + board[i][j + 2];
                    if(temp > max) max = temp;
                }
                //6. ㄴ자 막대 모양 - 5에서 상하반전
                if (i + 1 < N && j + 2 < M) {
                    temp = board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+1][j + 2];
                    if(temp > max) max = temp;
                }
                //7. ㄴ자 막대 모양 - 6에서 좌우반전
                if (i + 1 < N && j + 2 < M) {
                    temp = board[i+1][j] + board[i+1][j+1] + board[i+1][j+2] + board[i][j + 2];
                    if(temp > max) max = temp;
                }
                //8. ㄴ자 막대 모양 - 7에서 상하반전
                if (i + 1 < N && j + 2 < M) {
                    temp = board[i][j] + board[i][j+1] + board[i][j+2] + board[i+1][j + 2];
                    if(temp > max) max = temp;
                }
                //z자 막대 모양 - 1
                if (i + 2 < N && j + 1 < M) {
                    temp = board[i][j] + board[i+1][j] + board[i+1][j+1] + board[i+2][j + 1];
                    if(temp > max) max = temp;
                }
                //z자 막대 모양 - 2
                if (i + 2 < N && j + 1 < M) {
                    temp = board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+2][j];
                    if(temp > max) max = temp;
                }
                //z자 막대 모양 - 3
                if (i + 1 < N && j + 2 < M) {
                    temp = board[i+1][j] + board[i][j+1] + board[i+1][j+1] + board[i][j + 2];
                    if(temp > max) max = temp;
                }
                //z자 막대 모양 - 4
                if (i + 1 < N && j + 2 < M) {
                    temp = board[i][j] + board[i][j+1] + board[i+1][j+1] + board[i+1][j + 2];
                    if(temp > max) max = temp;
                }
                //ㅗ자 막대 모양 - 기본
                if (i + 1 < N && j + 2 < M) {
                    temp = board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+1][j + 2];
                    if(temp > max) max = temp;
                }
                //ㅜ자 막대 모양 - (상하반전)
                if (i + 1 < N && j + 2 < M) {
                    temp = board[i][j] + board[i][j+1] + board[i][j+2] + board[i+1][j + 1];
                    if(temp > max) max = temp;
                }
                //ㅏ자 막대 모양 - (회전)
                if (i + 2 < N && j + 1 < M) {
                    temp = board[i][j] + board[i+1][j] + board[i+2][j] + board[i+1][j + 1];
                    if(temp > max) max = temp;
                }
                //ㅓ자 막대 모양 - (회전)
                if (i + 2 < N && j + 1 < M) {
                    temp = board[i][j+1] + board[i+1][j] + board[i+1][j+1] + board[i+2][j + 1];
                    if(temp > max) max = temp;
                }


            }

        }
        bw.write(Integer.toString(max));
        bw.flush();
        bw.close();
    }
}