[백준] 4920 테트리스 게임 - Java

문제

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

 

---

 

문제 설명

이 문제는 테트리스 블록 중 하나를 N x N 크기의 표에 놓아 블록 아래에 있는 숫자의 합이 최대가 되도록 배치할 때, 그 최대 합을 구하는 문제입니다. 주어지는 블록은 총 5종류이고, 90도씩 회전할 수 있어 각기 다른 형태를 갖습니다.

문제 풀이

이 문제에서는 다음과 같은 과정을 통해 최댓값을 찾습니다:

1. 블록의 모든 가능한 형태 정의
   블록을 회전시키면 최대 4가지 형태가 생깁니다. 모든 회전 형태를 미리 정의해두고 사용합니다.
2. 모든 위치에 블록을 놓아본 후 합 계산
   각 위치에 대해 모든 블록의 형태를 적용해보고, 표 안에 들어가는 경우에만 블록이 차지하는 네 개의 위치 값을 더하여 합을 계산합니다.
3. 최댓값 갱신
   계산한 합이 이전 최댓값보다 크면 그 값을 최댓값으로 갱신합니다.
4. 테스트 케이스마다 반복
   표의 크기가 0이 주어질 때까지 위의 작업을 반복합니다.

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

public class Main {
    static int[][][] standard = {
            {{0, 0, 0, 0}, {0, 1, 2, 3}},
            {{0, 1, 2, 3}, {0, 0, 0, 0}},
            {{0, 0, 1, 1}, {0, 1, 1, 2}},
            {{0, 1, 1, 2}, {0, 0, -1, -1}},
            {{0, 0, 0, 1}, {0, 1, 2, 2}},
            {{0, 1, 2, 2}, {0, 0, 0, -1}},
            {{0, 1, 1, 1}, {0, 0, 1, 2}},
            {{0, 0, 1, 2}, {0, 1, 0, 0}},
            {{0, 1, 1, 1}, {0, -1, 0, 1}},
            {{0, 1, 1, 2}, {0, 0, 1, 0}},
            {{0, 0, 0, 1}, {0, 1, 2, 1}},
            {{0, 1, 1, 2}, {0, -1, 0, 0}},
            {{0, 0, 1, 1}, {0, 1, 1, 0}},
    };
    static int[][] board;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int idx = 1;
        while ((N = Integer.parseInt(br.readLine().trim())) != 0) {
            board = new int[N][N];
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine().trim());
                for (int j = 0; j < N; j++) {
                    board[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            // 모든 위치에 대해 블록을 놓아보고 최댓값 갱신
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    for (int a = 0; a < standard.length; a++) {
                        int sum = 0;
                        boolean flag = true;

                        // 블록의 네 개 칸에 대한 위치 확인 및 합 계산
                        for (int b = 0; b < 4; b++) {
                            int nx = i + standard[a][0][b];
                            int ny = j + standard[a][1][b];
                            if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
                                sum += board[nx][ny];
                            } else {
                                flag = false;
                                break;
                            }
                        }

                        // 유효한 위치에 놓을 수 있는 경우 최댓값 갱신
                        if (flag) {
                            max = Math.max(max, sum);
                        }
                    }
                }
            }
            System.out.println(idx + ". " + max);
            idx++;
        }
    }
}