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

풀이

이 문제를 처음 접근할떄는 어떠한 규칙이 있는지 확인 하였다. 그러나 문득 어느 한점에서 DFS처럼 갈수있는 공간을 하나씩 만들다보면 테트로노미노를 대칭 혹은 회전시킨 도형이 나온다는것을 알아차리고 DFS로 하였다. 물론 이러면서 중복이 발생하는 경우도 있었지만 신경쓰지 않고 진행하였다. 그리고 마지막으로 ㅗ모양을 따로 처리를 해주어야 한다. 또한 중간에 Math.max함수를 사용할수 있음에도 사용하지 않은 이유는 풀이시간이 차이가 나기때문이다. 처음 통과하였을떄는 Math.max를 하였는 결과값이고 두번째는 삼항연산자로 하였는것이다.

 

코드

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

class Main {
    static int[][] arr;
    static boolean[][] visit;
    static int N, M;
    static int result = Integer.MIN_VALUE;
    static int[] dir_I = {-1, 0, 1, 0};
    static int[] dir_J = {0, 1, 0, -1};

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

        arr = new int[N + 2][M + 2];
        visit = new boolean[N + 2][M + 2];

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

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                visit[i][j] = true;
                DFS1(1, i, j, arr[i][j]);
                extra(i, j);
                visit[i][j] = false;
            }
        }


        System.out.println(result);

    }

    public static void DFS1(int depth, int I, int J, int sum) {
        if (depth == 4) {
            result = (result > sum) ? result : sum;
        } else {
            int temp_I, temp_J;
            for (int k = 0; k < 4; k++) {
                temp_I = I + dir_I[k];
                temp_J = J + dir_J[k];
                if (check(temp_I, temp_J) && !visit[temp_I][temp_J]) {
                    visit[temp_I][temp_J] = true;
                    DFS1(depth + 1, temp_I, temp_J, sum + arr[temp_I][temp_J]);
                    visit[temp_I][temp_J] = false;
                }

            }
        }
    }

    public static void extra(int i, int j) {
        int sum = -1;

        sum = arr[i][j] + arr[i - 1][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i][j - 1];
        for (int k = 0; k < 4; k++) {
            result = result > (sum - arr[i + dir_I[k]][j + dir_J[k]]) ? result : sum - arr[i + dir_I[k]][j + dir_J[k]];

        }

    }

    public static boolean check(int I, int J) {
        if (1 <= I && I <= N && 1 <= J && J <= M && arr[I][J] != 0)
            return true;
        else return false;
    }
}

결과