[백준] 14500

백준 14500번: 테트로미노 문제 풀이

이번 포스팅에서는 백준 14500번 문제인 "테트로미노" 문제를 해결하는 과정을 정리하겠습니다. 이 문제는 4가지 종류의 테트로미노 모양을 2차원 배열에서 최적의 위치에 배치하여 얻을 수 있는 최대 합을 구하는 문제입니다.

문제 분석

문제는 주어진 2차원 배열에 다양한 테트로미노 모양을 놓았을 때, 합이 최대가 되는 경우를 찾는 것입니다. 테트로미노는 다양한 모양을 가지고 있으며, 이 문제에서는 총 5가지의 모양이 주어집니다.

테트로미노 모양 분석

1. 1자형 (I 모양)
2. 정사각형 (O 모양)
3. ㄴ자형 (L, J 모양)
4. ㄹ자형 (Z, S 모양)
5. ㅗ자형 (T 모양)

각 테트로미노는 회전이나 대칭을 통해 다양한 배치를 가질 수 있습니다. 모든 가능한 배치를 고려하여 최대 합을 구하는 것이 목표입니다.

해결 전략

문제를 해결하기 위해 각 테트로미노 모양에 대해 배열의 모든 위치에서 놓아보고 그 합을 계산한 후, 최대값을 구합니다. 이를 위해 각 테트로미노의 형태를 함수로 나누어 처리했습니다.

코드 구현

문제를 해결하기 위한 코드는 아래와 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class P14500 {

    // ㅗ, ㅜ, ㅓ, ㅏ 모양 테트로미노 처리
    private static int S345(int[][] table, int n, int m) {
        int sum = 0;

        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < m - 2; j++) {
                sum = Math.max(sum, table[i][j] + table[i][j+1] + table[i][j+2] + table[i+1][j]);
                sum = Math.max(sum, table[i][j] + table[i][j+1] + table[i][j+2] + table[i+1][j+1]);
                sum = Math.max(sum, table[i][j] + table[i][j+1] + table[i][j+2] + table[i+1][j+2]);

                sum = Math.max(sum, table[i+1][j] + table[i+1][j+1] + table[i+1][j+2] + table[i][j]);
                sum = Math.max(sum, table[i+1][j] + table[i+1][j+1] + table[i+1][j+2] + table[i][j+1]);
                sum = Math.max(sum, table[i+1][j] + table[i+1][j+1] + table[i+1][j+2] + table[i][j+2]);

                sum = Math.max(sum, table[i][j] + table[i][j+1] + table[i+1][j+1] + table[i+1][j+2]);
                sum = Math.max(sum, table[i][j+1] + table[i][j+2] + table[i+1][j] + table[i+1][j+1]);
            }
        }

        for (int i = 0; i < n - 2; i++) {
            for (int j = 0; j < m - 1; j++) {
                sum = Math.max(sum, table[i][j] + table[i+1][j] + table[i+2][j] + table[i][j+1]);
                sum = Math.max(sum, table[i][j] + table[i+1][j] + table[i+2][j] + table[i+1][j+1]);
                sum = Math.max(sum, table[i][j] + table[i+1][j] + table[i+2][j] + table[i+2][j+1]);

                sum = Math.max(sum, table[i][j] + table[i][j+1] + table[i+1][j+1] + table[i+2][j+1]);
                sum = Math.max(sum, table[i+1][j] + table[i][j+1] + table[i+1][j+1] + table[i+2][j+1]);
                sum = Math.max(sum, table[i+2][j] + table[i][j+1] + table[i+1][j+1] + table[i+2][j+1]);

                sum = Math.max(sum, table[i][j] + table[i+1][j] + table[i+1][j+1] + table[i+2][j+1]);
                sum = Math.max(sum, table[i+1][j] + table[i+2][j] + table[i][j+1] + table[i+1][j+1]);
            }
        }

        return sum;
    }

    // 정사각형 모양 테트로미노 처리
    private static int S2(int[][] table, int n, int m) {
        int sum = 0;

        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < m - 1; j++) {
                sum = Math.max(sum, table[i][j] + table[i][j+1] + table[i+1][j] + table[i+1][j+1]);
            }
        }

        return sum;
    }

    // I 모양 테트로미노 처리
    private static int S1(int[][] table, int n, int m) {
        int sum = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m - 3; j++) {
                sum = Math.max(sum, table[i][j] + table[i][j+1] + table[i][j+2] + table[i][j+3]);
            }
        }

        for (int i = 0; i < n - 3; i++) {
            for (int j = 0; j < m; j++) {
                sum = Math.max(sum, table[i][j] + table[i+1][j] + table[i+2][j] + table[i+3][j]);
            }
        }

        return sum;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] l0 = br.readLine().split(" "); 
        int n = Integer.parseInt(l0[0]);
        int m = Integer.parseInt(l0[1]);

        int[][] table = new int[n][m];

        for (int i = 0; i < n; i++) {
            l0 = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                table[i][j] = Integer.parseInt(l0[j]);
            }
        }

        int result = S1(table, n, m);

        int count = S2(table, n, m);
        result = Math.max(result, count);

        count = S345(table, n, m);
        result = Math.max(result, count);

        System.out.println(result);
    }
}

코드 설명

1. 함수별 테트로미노 모양 처리:

   • S1 함수는 I 모양 테트로미노의 최대 합을 계산합니다. 배열 내에서 가로 또는 세로로 연속된 4개의 칸을 합산합니다.
   • S2 함수는 정사각형 모양의 테트로미노 합을 계산합니다. 배열 내에서 2x2 영역의 합을 구합니다.
   • S345 함수는 ㄴ자형, ㄹ자형, ㅗ자형 모양의 테트로미노에 대해 가능한 모든 배치를 계산합니다.

2. 최대값 계산:

   • 각 함수에서 계산된 최대 합을 비교하여 최종 결과를 도출합니다.

사고 흐름 정리

1. 문제 분석: 주어진 배열에서 테트로미노를 놓아 최대 합을 구하기 위해 가능한 모든 배치를 탐색해야 합니다.

2. 테트로미노 모양 별 함수 분리: 각 테트로미노 모양에 대해 별도의 함수를 작성하여 코드의 가독성을 높이고, 최대값을 효율적으로 계산할 수 있도록 했습니다.

3. 최대값 비교: 각각의 함수에서 구한 값 중에서 가장 큰 값을 최종 결과로 출력합니다.

마무리

이번 문제는 다양한 테트로미노 모양을 고려해야 하는 복잡한 문제였지만, 각 모양을 함수로 분리하여 효율적으로 해결할 수 있었습니다. 테트로미노 모양을 분석하고, 모든 가능한 배치를 탐색하는 과정이 중요한 문제였습니다. 이번 포스팅을 통해 문제 해결 방법을 이해하는 데 도움이 되었기를!