백 준 - 14500

문제 : www.acmicpc.net/problem/14500

14500번: 테트로미노

 

문제는 다음과 같습니다.

 

문제에서 요구하는 것은 주어진 배열에서 어떠한 테트로미노를 1개만 설치하였을 때 가장 큰 값을 가지는가 입니다.

 

먼저 모든 테트로미노를 좌우 및 상하로 회전한 모든 경우를 배열에서 검사하기에는 코드가 너무 복잡하고 힘들 것 같습니다.

여기서 아래의 테트로미노를 제외하면 

 

테트로미노를 상하좌우 회전 및 뒤집은 경우를 생각하면 그냥 상, 하 , 좌 , 우 로 1칸씩 이동하는 모든 경우가 가능하다라는 것을 알 수 있습니다.

 

그래서 이를 제귀로 구현하고 위에서의 예외는 따로 처리해주도록 하겠습니다.

전체적인 코드는 다음과 같습니다.

import java.util.*;

public class Main {

    // 문제 14500

    public static int[][] arr;
    public static int maxValue = -1;
    public static int[] dx = new int[]{0 , 0 , 1, -1};
    public static int[] dy = new int[]{1 , -1 , 0, 0};

    public static void main(String[] args) {

        Scanner stdin = new Scanner(System.in);

        int n = stdin.nextInt();
        int m = stdin.nextInt();

        arr = new int[n][m];
        boolean[][] flag = new boolean[n][m];

        for (int i = 0 ; i < n ; i++) {

            for(int j = 0 ; j < m ; j++) {

                arr[i][j] = stdin.nextInt();
            }
        }

        for(int i = 0 ; i < arr.length ; i++) {

            for(int j = 0 ; j < arr[0].length ; j++) {

                flag[i][j] = true;

                move(j , i , arr[i][j] , 0 , flag);

                flag[i][j] = false;
            }
        }

        maxValue = Math.max(maxValue , searchExcept1());
        maxValue = Math.max(maxValue , searchExcept2());
        maxValue = Math.max(maxValue , searchExcept3());
        maxValue = Math.max(maxValue , searchExcept4());

        System.out.println(maxValue);
    }


    //중복이 있어서는 안된다
    public static void move(int x, int y , int value , int idx , boolean[][] flag) {

        // 4칸 모두 움직임
        if (idx == 3) {

            maxValue = Math.max(maxValue , value);

            return;
        }

        for (int i = 0 ; i < 4 ; i++) {

            int nextY = y + dy[i];
            int nextX = x + dx[i];

            if ((nextY < arr.length && nextY >= 0 ) && (nextX < arr[0].length && nextX >= 0) ) {

                if (flag[nextY][nextX] == false) {

                    flag[nextY][nextX] = true;

                    // 4방향 중에서 1방향으로 움직임
                    move(nextX , nextY , value + arr[nextY][nextX] , idx+1 , flag);

                    flag[nextY][nextX] = false;

                }
            }


        }

    }

    public static int searchExcept1() {

        int max_Val = 0;

        for (int i = 0 ; i < arr.length-1 ; i++) {

            for(int j = 0 ; j < arr[0].length - 2 ; j++) {

                int val = arr[i][j] + arr[i][j+1] + arr[i+1][j+1]+ arr[i][j+2];

                max_Val = Math.max(max_Val , val);
            }
        }

        return max_Val;
    }

    public static int searchExcept2() {

        int max_Val = 0;

        for (int i = 1 ; i < arr.length ; i++) {

            for(int j = 0 ; j < arr[0].length - 2 ; j++) {

                int val = arr[i][j] + arr[i][j+1] + arr[i-1][j+1]+ arr[i][j+2];

                max_Val = Math.max(max_Val , val);
            }
        }

        return max_Val;
    }

    public static int searchExcept3() {

        int max_Val = 0;

        for (int i = 0 ; i < arr.length - 2 ; i++) {

            for(int j = 0 ; j < arr[0].length - 1 ; j++) {

                int val = arr[i][j] + arr[i+1][j] + arr[i+1][j+1]+ arr[i+2][j];

                max_Val = Math.max(max_Val , val);
            }
        }

        return max_Val;
    }

    public static int searchExcept4() {

        int max_Val = 0;

        for (int i = 0 ; i < arr.length - 2 ; i++) {

            for(int j = 1 ; j < arr[0].length  ; j++) {

                int val = arr[i][j] + arr[i+1][j] + arr[i+1][j-1]+ arr[i+2][j];

                max_Val = Math.max(max_Val , val);
            }
        }

        return max_Val;

    }
}

 

제귀로 그냥 상화좌우를 4칸 움직이도록 해서 배열에서 움직인 칸들의 합을 구해서 최댓값을 비교 및 갱신하도록 합니다.

예외로는 1가지 테트로미노인데 이를 상, 화 , 좌 , 우 반전 및 회전한 4가지 경우를 배열안에서 모두 검사하도록 합니다.