[백준] 14500번 - 테트로미노 [Java]

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

 

[백준] 14500번 - 테트로미노 [Java]

[백준] 14500번 - 테트로미노 [Java]

---

1.  아이디어

 

모든 테트로미노의 모양을 미리 구한 후 각각에 대해 종이에 순회하며 계산하는 방식으로 구현했다.

---

2. 문제풀이

 

init 메서드로 모든 테트로미노의 모양을 2차원 배열로 구해서 List에 담았다. init은 5가지 기본 모양을 2차원 배열로 만든 후 90도, 180도, 270도 회전 메서드와 좌우반전 메서드를 작성해서 이 기본 모양을 회전 및 반전시켜 모든 테트로미노의 모양을 구했다.

 

테트로미노의 경우의 수

- 하늘색 테트로미노는 기본 모양, 90도 회전, 총 2가지

- 노란색 테트로미노는 기본 모양, 총 1가지

- 주황색 테트로미노는 기본 모양, 90도 회전, 180도 회전, 270도 회전, 반전 모양, 반전+90도 회전, 반전+180도 회전, 반전+270도 회전, 총 8가지

- 초록색 테트로미노는 기본 모양, 90도 회전, 반전 모양, 반전+90도 회전, 총 4가지

- 분홍색 테트로미노는 기본 모양, 90도 회전, 180도 회전, 270도 회전, 총 4가지

---

3. 코드

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        List<boolean[][]> tetrominoList = init();

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

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

        int max = 0;
        for (boolean[][] tetromino : tetrominoList) {
            int height = tetromino.length;
            int width = tetromino[0].length;

            for (int i = 0; i <= N - height; i++) {
                for (int j = 0; j <= M - width; j++) {
                    int sum = 0;

                    for (int a = 0; a < height; a++) {
                        for (int b = 0; b < width; b++) {
                            if (tetromino[a][b]) sum += map[i + a][j + b];
                        }
                    }

                    max = Math.max(max, sum);
                }
            }
        }

        System.out.println(max);
    }

    private static List<boolean[][]> init() {
        List<boolean[][]> list = new ArrayList<>();

        boolean[][] type1 = new boolean[][]{{true, true, true, true}};
        boolean[][] type2 = new boolean[][]{{true, true}, {true, true}};
        boolean[][] type3 = new boolean[][]{{true, false}, {true, false}, {true, true}};
        boolean[][] type4 = new boolean[][]{{true, false}, {true, true}, {false, true}};
        boolean[][] type5 = new boolean[][]{{false, true, false}, {true, true, true}};
        boolean[][] flippedType3 = flip(type3);
        boolean[][] flippedType4 = flip(type4);

        list.add(type1);
        list.add(rotate90(type1));

        list.add(type2);

        list.add(type3);
        list.add(rotate90(type3));
        list.add(rotate180(type3));
        list.add(rotate270(type3));
        list.add(flippedType3);
        list.add(rotate90(flippedType3));
        list.add(rotate180(flippedType3));
        list.add(rotate270(flippedType3));

        list.add(type4);
        list.add(rotate90(type4));
        list.add(flippedType4);
        list.add(rotate90(flippedType4));

        list.add(type5);
        list.add(rotate90(type5));
        list.add(rotate180(type5));
        list.add(rotate270(type5));

        return list;
    }

    private static boolean[][] rotate90(boolean[][] matrix) {
        int H = matrix.length;
        int W = matrix[0].length;
        boolean[][] newMatrix = new boolean[W][H];

        for (int i = 0; i < W; i++) {
            for (int j = 0; j < H; j++) {
                newMatrix[i][j] = matrix[H - 1 - j][i];
            }
        }

        return newMatrix;
    }

    private static boolean[][] rotate180(boolean[][] matrix) {
        int H = matrix.length;
        int W = matrix[0].length;
        boolean[][] newMatrix = new boolean[H][W];

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                newMatrix[i][j] = matrix[H - 1 - i][W - 1 - j];
            }
        }

        return newMatrix;
    }

    private static boolean[][] rotate270(boolean[][] matrix) {
        int H = matrix.length;
        int W = matrix[0].length;
        boolean[][] newMatrix = new boolean[W][H];

        for (int i = 0; i < W; i++) {
            for (int j = 0; j < H; j++) {
                newMatrix[i][j] = matrix[j][W - 1 - i];
            }
        }

        return newMatrix;
    }

    private static boolean[][] flip(boolean[][] matrix) {
        int H = matrix.length;
        int W = matrix[0].length;
        boolean[][] newMatrix = new boolean[H][W];

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                newMatrix[i][j] = matrix[i][W - 1 - j];
            }
        }

        return newMatrix;
    }

}

---

4. 후기