[백준 14500] 테트로미노(JAVA)

백준 14500번 문제 - 테트로미노

14500번: 테트로미노

---

문제 분석 

 

 

• 블록은 5가지가 있다.
  • 회전, 대칭 가능
• N x M인 판(테트로미노)가 있다. 각 칸에는 숫자가 적혀있다.
• 블록을 둬서 블록이 차지하는 칸의 합이 결과 값이라고 할 때, 해당 테트로미노에서 얻을 수 있는 가장 큰 결과 값을 출력해라.

---

 

해결 포인트

 

• 완전 탐색
• 블록 클래스 구현
  • 블록의 첫번째 칸을 0,0이라했을 때 칸 4개의 x의 변화 y의 변화를 저장한다.
  • ex) 가로로 긴 배열은 (0,0) (1,0) (2,0) (3,0) 4개의 칸이 있다. 
    이 때 dx = {0,1,2,3} | dy = {0,0,0,0} 이다.
• 판의 (0,0)부터 (N-1, M-1) 칸까지 해당 칸이 시작점일 경우, 해당 블록이 낼 수 있는 최대 결과 값을 알아낸다.
• 블록의 최댓값은 해당 블록의 getCount 함수로 구현하였다.
  • 인자 값 : 시작 x, 시작 y
  • 회전 확인 : 이 때 모든 칸의 값을 합쳐서 구한다.
    • ndx, ndy는 회전 설정 값이다.
    • int nx = sx + dx[j] * ndx[i]
    • int ny = sy + dy[j] * ndy[i] 
  • 대칭 확인 : 대칭한 값은 초기 칸 변화를 dx, dy를 바꿔서 설정한다.
    • ndx, ndy는 회전 설정 값이다.
    • int nx = sx + dy[j] * ndx[i]
    • int ny = sy + dx[j] * ndy[i] 
• 알아낸 후, 현재 최댓값과 비교 후 더 크면 변경한다.

---

 

코드

 

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

public class Main {
    public static int[][] nums;
    public static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        nums = new int[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                nums[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        ArrayList<Block> blocks = new ArrayList<>();

        blocks.add(new Block(new int[]{0, 1, 2, 3}, new int[]{0, 0, 0, 0}));
        blocks.add(new Block(new int[]{0, 1, 2, 2}, new int[]{0, 0, 0, -1}));
        blocks.add(new Block(new int[]{0, 0, 1, 1}, new int[]{0, 1, 0, 1}));
        blocks.add(new Block(new int[]{0, 1, 1, 2}, new int[]{0, 0, -1, -1}));
        blocks.add(new Block(new int[]{0, 1, 2, 1}, new int[]{0, 0, 0, 1}));

        int max = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                for (Block block : blocks) {
                    max = Math.max(max, block.getCount(j, i));
                }
            }
        }

        bw.write(max + "\n");

        bw.flush();
        bw.close();
    }

    public static class Block {
        int [] dx;
        int [] dy;

        public Block(int [] dx, int [] dy) {
            this.dx = dx;
            this.dy = dy;
        }

        public int getCount(int sx, int sy) {
            int maxCount = 0;
            int count;

            int []ndx = {1,1,-1,-1};
            int []ndy = {1,-1,1,-1};

            for (int i = 0; i < 4; i++) {
                count = 0;
                for (int j = 0; j < 4; j++) {
                    int nx = sx + dx[j] * ndx[i];
                    int ny = sy + dy[j] * ndy[i];
                    if (!checkRound(nx, ny)) {
                        continue;
                    }
                    count += nums[ny][nx];
                }
                maxCount = Math.max(maxCount, count);
            }

            for (int i = 0; i < 4; i++) {
                count = 0;
                for (int j = 0; j < 4; j++) {
                    int nx = sx + dy[j] * ndx[i];
                    int ny = sy + dx[j] * ndy[i];
                    if (!checkRound(nx, ny)) {
                        continue;
                    }
                    count += nums[ny][nx];
                }
                maxCount = Math.max(maxCount, count);
            }

            return maxCount;
        }
    }

    public static boolean checkRound(int x, int y) {
        return x >= 0 && y >= 0 && x < M && y < N;
    }
}