[BJ]테트로미노 _14500

 

풀이 핵심

도형을 회전시키는 방법
int[] position은 r,c 정보를 담고 있을 때, (r,c) -> (c, size - r - 1)
여기서 size는 어떤 정사각형에 도형이 담겨있다고 생각할 때 한변의 길이를 의미한다.
위 공식을 사용하면 회전을 하고, 만약 ㅗ 모양이 회전해서 ㅏ 모양이 되었을 때
[ (0,1), (1,0), (1,1), (1,2) ] => [ (0,1), (1,1), (1,2), (2,1) ] 이된다.
여기서 setStartPoint함수가 하는 역할은 정사각형 안에 도형을 왼쪽 끝에 맞출 수 있도록 설정하는 것이다. 
[ (0,1), (1,1), (1,2), (2,1) ] => [ (0,0), (1,0), (1,1), (2,0) ]

 

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

public class Main {
    static int N,M, map[][], ans=0;
    static Ttrno[] ttrnos;
 
    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());

        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());
            }
        }

        // 테트리노 모양,회전,반전 설정
        initTtrno();



        // 테트리노 모양 별로 맵을 순회하면서 시뮬레이션해본다.
        for (int i = 0; i < ttrnos.length; i++) {
            Ttrno curTtrno = ttrnos[i];

            if(!curTtrno.doInversion && !curTtrno.doRevor){ // 돌리거나 반전이 필요 없을때 1번만 돌리기.
                simul(curTtrno.position);
            }else{

                if(curTtrno.doRevor){ // 회전 해봐야하는거면 회전하고 시뮬 재실행
                    for (int j = 0; j < 4; j++) {

                        letRevor(curTtrno.position);
                        // 초기 시작점 맞추기.

                        setStartPoint(curTtrno.position);

                        simul(curTtrno.position);
                    }
                }
                // 반전도 해야하면 해보기.
                if(curTtrno.doInversion){
                    letInversion(curTtrno.position);
                    // 회전 시키면서 또 시뮬
                    for (int j = 0; j < 4; j++) {
                        letRevor(curTtrno.position);
                        setStartPoint(curTtrno.position);
                        simul(curTtrno.position);
                    }
                }
            }


        }

        System.out.println(ans);

    }



    public static void simul(int[][] position){
        int sum =0 ;

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                int tmpSum=0;
                // 모든 지점에서 도형모양으로 이동하면서 합을 계산한다.
                for (int k = 0; k < position.length; k++) {
                    int ni = i+position[k][0];
                    int nj = j+position[k][1];
                    if(!isOut(ni,nj)) {
                        tmpSum+=map[ni][nj];

                    }else {
                        tmpSum = 0;
                        break;
                    }

                }
                // 테트리노 모양대로 이동했을 때 계산된 합의 최대값을 갱신
                sum = Math.max(sum,tmpSum);
            }
        }
        // 최대를 답에 갱신.
        ans = Math.max(ans,sum);
    }

    public static void letRevor(int[][] position){
        int tSize = getTSize(position);

        for (int i = 0; i < position.length; i++) {
            int row = position[i][0];
            int col = position[i][1];
            // 회전 공식 적용
            int rRow = col;
            int rCol = tSize - row - 1;
            position[i][0] = rRow;
            position[i][1] = rCol;
        }

    }

    private static int getTSize(int[][] position) {
        int ts=0;
        for (int i = 0; i < position.length; i++) {
            ts = Math.max(ts, Math.max(position[i][0], position[i][1]));
        }
        return ts+1;
    }

    public static void letInversion(int[][] position){
        int size = position[0].length;

        for (int i = 0; i < position.length; i++) {
            int col = position[i][1];
            // 반전 공식 적용
            position[i][1] = size - col -1;
        }
    }


    private static void initTtrno() {
        ttrnos = new Ttrno[6];
        // 네모 : 회전, 반전 불필요.
        int[][] position = new int[][] {{0,0},{0,1},{1,0},{1,1}};
        ttrnos[0] = new Ttrno(false,false,position);
        // 1자 1번만 돌리면 되기 때문에 2개 넣을 것 모양 : ㅡ,ㅣ
        position = new int[][] {{0,0},{0,1},{0,2},{0,3}};
        ttrnos[1] = new Ttrno(false,false,position);
        position = new int[][] {{0,0},{1,0},{2,0},{3,0}};
        ttrnos[2] = new Ttrno(false,false,position);

        // ㄴ모양 : 회전 반전 둘다 필요
        position = new int[][] {{0,0},{1,0},{2,0},{2,1}};
        ttrnos[3] = new Ttrno(true,true,position);
        ttrnos[3].me=true;

        // ㅜ모양 : 회전만 필요
        position = new int[][] {{0,0},{0,1},{0,2},{1,1}};
        ttrnos[4] = new Ttrno(true,false,position);

        // 나머지 1개 모양은 회전, 반전 둘 다 필요.
        position = new int[][] {{0,0},{1,0},{1,1},{2,1}};
        ttrnos[5] = new Ttrno(true,true,position);
    }

    /**
     * 회전 : (r,c) -> (c, max(colSize, rowSize)-r-1);
     * 반전 : (r,c) -> (r, max(colSize) - c-1);
     * */
    static class Ttrno{
        // 회전해야하는지, 반전해야하는지
        boolean doRevor, doInversion,me;
        int[][] position = new int[4][2];
        public Ttrno(boolean doRevor, boolean doInversion, int[][] position){
            this.doRevor = doRevor;
            this.doInversion = doInversion;
            this.position = position;
        }
    }
    // 회전시킨 경우는 시작점을 (0,?) or (?,0) 으로 맞추기.
    public static void setStartPoint(int[][] position){

        int minR = 2000;
        int minC = 2000;
        for (int i = 0; i < position.length; i++) {
            minR = Math.min(minR,position[i][0]);
            minC = Math.min(minC,position[i][1]);
        }


        for (int i = 0; i < position.length; i++) {
            position[i][0]-=minR;
            position[i][1]-=minC;
        }
    }

    public static boolean isOut(int ni, int nj){
        return ni < 0 || ni >= N || nj < 0 || nj >= M;
    }
}