링크텍스트

테트로미노

대략설계
도형의 대칭 회전 2*4 총 8지씩 나오겠다고 생각했다. 그런데 dx dy를 그러면 총 8개씩이나 만들어야 하나 라고 생각 했는데. 일반 DFS전략 자체가 마름표 형식으로 퍼져나가는 것을 알고 여기에 다 포함되어 있겠다고 생각했다 하지만 일반 DFS는 방문하는 점을 되 돌리는 부분이 존재하지 않아 백트래킹 전략이 들어간 방법을 하면 될것 같았다. 하지만 마지막 테스트 케이스 3번째에서 답이 도출되지 않았다. 무엇이 문제인가 DFS전략을 뜯어보는 도중 방문한 점을 다시 false로 처리는 해주지만 한 도형만 도달하지 않는 것을 깨달았다.
이 부분도 함께 처리해야하는 건가 라는 생각을 하였지만 도저히 나오지 않아 관련 글을 참고하여 예외 과정을 구현하였다.

• 참조 https://yubh1017.tistory.com/47 (그림 설명이 아주 잘 되어 있습니다.)

package oneDay_twoSol.DB_FirstSearch;

import java.util.Scanner;

public class Tetromino {

    static int[][] ey = {{0, 0, 0, 1}, {1, 1, 1, 0}, {0, 1, 2, 1}, {0, 1, 2, 1}};
    static int[][] ex = {{0, 1, 2, 1}, {0, 1, 2, 1}, {1, 1, 1, 0}, {0, 0, 0, 1}};
    // 예외의 도형 . y축 x축.
    
    static int n, m;
    static int dy[] = {-1, 1, 0, 0};
    static int dx[] = {0, 0, -1, 1};
    // 위 아래 왼쪽 오른쪽
    static int max;
    static int board[][];
    static boolean visited[][];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        board = new int[n][m];
        visited = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                board[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dfs(i, j, 0, 0);
                except(i, j);
            }
        }
        System.out.println(max);
    }

    static void dfs(int y, int x, int depth, int sum) {

        if (depth == 4) {
            max = Math.max(max, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int tempY = y + dy[i];
            int tempX = x + dx[i];
            if (tempX >= 0 && tempY >= 0 && tempY < n && tempX < m) {
                if (!visited[tempY][tempX]) {
                    visited[tempY][tempX] = true;
                    dfs(tempY, tempX, depth + 1, sum + board[tempY][tempX]);
                    visited[tempY][tempX] = false;
                }
            }
        }
    }

    static void except(int y, int x) {
        int sum = 0;
        boolean check;
        for (int i = 0; i < 4; i++) {
            sum = 0;
            check = true;
            for (int j = 0; j < 4; j++) {
                int tempY = y + ey[i][j];
                int tempX = x + ex[i][j];
                if (tempX >= 0 && tempY >= 0 && tempY < n && tempX < m) {
                    sum += board[tempY][tempX];
                } else {
                    check = false;
                    break;
                }
            }
            if (check) {
                max = Math.max(max, sum);
            }
        }
    }

}