[BOJ] 14500 테트로미노 - Java

🤔 문제

---

 

14500번: 테트로미노

 

😀 풀이

---

위 문제는 적절한 구현과 완전 탐색을 하여 풀이하였습니다.

 

주어진 종이 정보에 도형 5가지를 각각 놓아보아야 하는데 이 때 각 도형을 회전, 대칭시켜서 놓아보는 작업 역시 해봐야 합니다. 

 

저의 풀이에서는 편의를 위해 도형을 회전하는 과정은 종이 정보를 회전하는 방식을 사용해 풀이했습니다. 

 

풀이 과정을 간략하게 요약하면 아래와 같습니다.

1.  종이의 모든 점에 도형을 하나씩 놓아본다.
2. 점수를 계산한다.

1번 과정에서 도형을 회전하고 대칭해보는 과정을 포함하면 문제 풀이가 가능합니다.

 

구현 문제다보니 긴 설명보다는 코드를  바로 올리도록 하겠습니다.

---

💻 전체 풀이 코드는 아래와 같습니다.

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

public class BOJ_14500 {

    static int[][] nemo = {{0, 0}, {1, 0}, {0, 1}, {1, 1}};
    static int[][] straight = {{0, 0}, {0, 1}, {0, 2}, {0, 3}};
    static int[][] nieun = {{0, 0}, {1, 0}, {2, 0}, {2, 1}};
    static int[][] nieun2 = {{0, 1}, {1, 1}, {2, 1}, {2, 0}};
    static int[][] riyl = {{0, 0}, {1, 0}, {1, 1}, {2, 1}};
    static int[][] riyl2 = {{0, 1}, {1, 1}, {1, 0}, {2, 0}};
    static int[][] tshape = {{0, 0}, {0, 1}, {0, 2}, {1, 1}};
    static int[][][] shapes = {nemo, straight, nieun, nieun2, riyl, riyl2, tshape};

    static int answer = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

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

        int[][] rotateNums1 = rotate(nums);
        int[][] rotateNums2 = rotate(rotateNums1);
        int[][] rotateNums3 = rotate(rotateNums2);

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                check(nums, i, j);
                check(rotateNums1, j, i);
                check(rotateNums2, i, j);
                check(rotateNums3, j, i);
            }
        }
        // 정답 출력
        System.out.println(answer);
    }

    // 맵 회전
    private static int[][] rotate(int[][] nums) {
        int x = nums[0].length;
        int y = nums.length;
        int[][] result = new int[x][y];

        for (int i = 0; i < x; i++)
            for (int j = 0; j < y; j++) {
                result[i][j] = nums[y - (j + 1)][i];
            }

        return result;
    }

    private static void check(int[][] arr, int yStart, int xStart) {
        int[] nx = new int[4];
        int[] ny = new int[4];
        int score;

        for (int[][] shape : shapes) {
            for (int j = 0; j < 4; j++) {
                nx[j] = shape[j][1] + xStart;
                ny[j] = shape[j][0] + yStart;
            }

            if (validCoordinate(nx, ny, arr)) {
                score = 0;
                for (int k = 0; k < 4; k++) {
                    score += arr[ny[k]][nx[k]];
                }
                answer = Math.max(score, answer);
            }
        }
    }

    // 맵을 벗어난 인덱스인지 체크
    private static boolean validCoordinate(int[] nx, int[] ny, int[][] arr) {
        for (int i = 0; i < 4; i++) {
            if (nx[i] < 0 || nx[i] >= arr[0].length || ny[i] < 0 || ny[i] >= arr.length)
                return false;
        }
        return true;
    }
}