[14500] - 테트로미노

문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

정사각형은 서로 겹치면 안 된다.

도형은 모두 연결되어 있어야 한다.

정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

코드

import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();

        int[][] map = new int[N][M];

        for (int i = 0; i < N ; i++) {
            for (int j = 0; j < M ; j++) {
                map[i][j] = scanner.nextInt();
            }
        }

        List<Integer> tetromino = List.of(1,2,3,4,5);

        recursion(map, tetromino, 0, 0);
        System.out.println(maxSum);
    }

    static int maxSum = 0;

    public static void recursion(int[][] map, List<Integer> tetromino, int x, int y) {
        if(y >= map.length || x >= map[y].length){
            return;
        }

        for (int i = 0; i < tetromino.size(); i++) {
            int currentSum = sum(map,tetromino.get(i), x, y);
            maxSum = Math.max(currentSum, maxSum);
        }

        if(x == map[y].length - 1){
            recursion(map, tetromino, 0, y + 1);
        }else{
            recursion(map, tetromino, x + 1, y);
        }
    }

    private static int sum(int[][] map, int tetrominoIndex, int x, int y){
        int sum = 0;
        switch (tetrominoIndex) {
            case 1:
                if (y + 3 < map.length) {
                    sum = Math.max(sum, map[y][x] + map[y + 1][x] + map[y + 2][x] + map[y + 3][x]);
                }

                if (x + 3 < map[y].length) {
                    sum = Math.max(sum, map[y][x] + map[y][x + 1] + map[y][x + 2] + map[y][x + 3]);
                }
                
                return sum;
            
            case 2:
                if (x + 1 < map[y].length && y + 1 < map.length) {
                    return map[y][x] + map[y][x + 1] + map[y + 1][x] + map[y + 1][x + 1];
                }
                
                return sum;
                
            case 3:
                if (x - 1 >= 0 && y - 2 >= 0) {
                    sum = Math.max(sum, map[y][x] + map[y][x - 1] + map[y - 1][x - 1] + map[y - 2][x - 1]);
                }

                if (x - 2 >= 0 && y - 1 >= 0) {
                    sum = Math.max(sum, map[y][x] + map[y - 1][x] + map[y - 1][x - 1] + map[y - 1][x - 2]);
                }

                if (y - 1 >= 0 && x + 2 < map[y].length) {
                    sum = Math.max(sum, map[y][x] + map[y - 1][x] + map[y - 1][x + 1] + map[y - 1][x + 2]);
                }

                if (x + 1 < map[y].length && y - 2 >= 0) {
                    sum = Math.max(sum, map[y][x] + map[y][x + 1] + map[y - 1][x + 1] + map[y - 2][x + 1]);
                }

                if (x - 1 >= 0 && y + 2 < map.length) {
                    sum = Math.max(sum, map[y][x] + map[y][x - 1] + map[y + 1][x - 1] + map[y + 2][x - 1]);
                }

                if (y + 1 < map.length && x - 2 >= 0) {
                    sum = Math.max(sum, map[y][x] + map[y + 1][x] + map[y + 1][x - 1] + map[y + 1][x - 2]);
                }

                if (y + 1 < map.length && x + 2 < map[y].length) {
                    sum = Math.max(sum, map[y][x] + map[y + 1][x] + map[y + 1][x + 1] + map[y + 1][x + 2]);
                }

                if (x + 1 < map[y].length && y + 2 < map.length) {
                    sum = Math.max(sum, map[y][x] + map[y][x + 1] + map[y + 1][x + 1] + map[y + 2][x + 1]);
                }
                
                return sum;

            case 4:
                if(x - 1 >= 0 && y - 2 >= 0){
                    sum = Math.max(sum, map[y][x] + map[y-1][x] + map[y-1][x-1] + map[y-2][x-1]);
                }

                if(x + 1 < map[y].length && y - 2 >= 0){
                    sum = Math.max(sum, map[y][x] + map[y-1][x] + map[y-1][x+1] + map[y-2][x+1]);
                }

                if(x - 2 >= 0 && y + 1 < map.length){
                    sum = Math.max(sum, map[y][x] + map[y][x-1] + map[y+1][x-1] + map[y+1][x-2]);
                }

                if(x + 2 < map[y].length && y + 1 < map.length){
                    sum = Math.max(sum, map[y][x] + map[y][x+1] + map[y+1][x+1] + map[y+1][x+2]);
                }

                return  sum;

            case 5:
                if(x + 1 < map[y].length && x - 1 >= 0 && y - 1 >= 0){
                    sum = Math.max(sum, map[y][x] + map[y][x-1] + map[y][x+1] + map[y-1][x]);
                }

                if(x - 1 >= 0 && y - 1 >= 0 && y + 1 < map.length){
                    sum = Math.max(sum, map[y][x] + map[y][x-1] + map[y-1][x] + map[y+1][x]);
                }

                if(x + 1 < map[y].length && y - 1 >= 0 && y + 1 < map.length){
                    sum = Math.max(sum, map[y][x] + map[y][x+1] + map[y-1][x] + map[y+1][x]);
                }

                if(x + 1 < map[y].length && x - 1 >= 0 && y + 1 < map.length){
                    sum = Math.max(sum, map[y][x] + map[y][x-1] + map[y][x+1] + map[y+1][x]);
                }
                
                return sum;
        }
        throw new RuntimeException();
    }
}

테스트 코드

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

import java.util.List;

import static org.junit.jupiter.api.Assertions.*;

class MainTest {
    List<Integer> tetromino = List.of(1,2,3,4,5);

    @BeforeEach
    void initialize(){
        Main.maxSum = 0;
    }

    @Test
    @DisplayName("14500 TestCase 1")
    void Test1(){
        int[][] map = new int[][]{{1,2,3,4,5},{5,4,3,2,1},{2,3,4,5,6},{6,5,4,3,2},{1,2,1,2,1}};

        Main.recursion(map,tetromino,0,0);

        assertEquals(19, Main4.maxSum);
    }

    @Test
    @DisplayName("14500 TestCase 2")
    void Test2(){
        int[][] map = new int[][]{{1,2,3,4,5},{1,2,3,4,5},{1,2,3,4,5},{1,2,3,4,5},{1,2,3,4,5}};

        Main.recursion(map, tetromino, 0, 0);

        assertEquals(20, Main4.maxSum);
    }

    @Test
    @DisplayName("14500 TestCase 3")
    void Test3(){
        int[][] map = new int[][]{{1,2,1,2,1,2,1,2,1,2},{2,1,2,1,2,1,2,1,2,1},{1,2,1,2,1,2,1,2,1,2},{2,1,2,1,2,1,2,1,2,1}};

        Main.recursion(map,tetromino,0,0);

        assertEquals(7, Main4.maxSum);
    }
}