백준 14500 - Java

내 첫 풀이 : 

처음에 모양을 정의하고 그거랑 비교하면서 최대값을 구하는 방식으로 풀었으나 계속 오류가 떳고 해결이 안되어서 구글링을 해보니 다들 DFS와 BackTrack을 썻기에 나도 그거에 맞춰서 풀었다. 아마도 모양이 예외가 더 있는거 같은데 찾지를 못했다.

import java.util.Scanner;

public class BJ14500 {
    //미리 포리오미노를 만들고 나중에 비교할 것임.
    static int[][][] tetrominoes = {
            {{0, 0}, {0, 1}, {0, 2}, {0, 3}}, {{0, 0}, {1, 0}, {2, 0}, {3, 0}},  // ㅡ 모양
            {{0, 0}, {0, 1}, {1, 0}, {1, 1}},                                     // ㅁ 모양
            {{0, 0}, {1, 0}, {2, 0}, {2, 1}}, {{0, 1}, {1, 1}, {2, 1}, {2, 0}},  // L 모양
            {{0, 0}, {1, 0}, {2, 0}, {1, 1}}, {{0, 0}, {1, -1}, {1, 0}, {1, 1}}, // ㅗ 모양
            {{0, 0}, {0, 1}, {0, 2}, {1, 0}}, {{0, 0}, {0, 1}, {0, 2}, {1, 2}},  // ㄴ 모양
            {{0, 0}, {1, 0}, {1, 1}, {2, 1}}, {{0, 0}, {0, 1}, {-1, 1}, {-1, 2}} // ㄹ 모양
    };


    static int[][] arr;
    static int N, M, maxSum = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        arr = new int[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                checkTetrominoes(i, j);
            }
        }

        System.out.println(maxSum);
    }
    private static void checkTetrominoes(int x, int y) {
        //(0,0)~(0,3) 계산
        for (int[][] tetrominoe : tetrominoes) {
            int sum = 0;
            boolean isValid = true;
            for (int k = 0; k < tetrominoe.length; k++) {
                int x1 = x + tetrominoe[k][0];
                int y1 = y + tetrominoe[k][1];
                //전체 배열 크기 벗어나면 멈춘다.
                if (x1 < 0 || y1 < 0 || x1 >= N || y1 >= M) {
                    isValid = false;
                    break;
                }

                sum += arr[x1][y1];
            }
            //범위를 벗어나지 않으면 큰값 저장.
            if (isValid) {
                maxSum = Math.max(maxSum, sum);
            }
        }
    }
}

 

2번째 풀이 :

import java.util.Scanner;

public class BJ14500 {
    static int[][] arr;
    static boolean[][] visited;
    static int N, M, maxSum = 0;
    static int[] dx = {0, 1, 0, -1}; // 상하좌우 이동
    static int[] dy = {1, 0, -1, 0};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        arr = new int[N][M];
        visited = new boolean[N][M];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        // 모든 시작점에 대해 DFS 수행
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visited[i][j] = true;
                dfs(i, j, 0, arr[i][j]);
                visited[i][j] = false;

                // ㅗ 모양 처리 (특수 케이스)
                checkSpecialShape(i, j);
            }
        }

        System.out.println(maxSum);
    }

    // DFS로 테트로미노의 합 계산
    private static void dfs(int x, int y, int depth, int sum) {
        if (depth == 3) { // 테트로미노의 4칸을 탐색했으면 종료
            maxSum = Math.max(maxSum, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            // 유효 범위 및 방문 여부 확인
            if (nx >= 0 && ny >= 0 && nx < N && ny < M && !visited[nx][ny]) {
                visited[nx][ny] = true;
                dfs(nx, ny, depth + 1, sum + arr[nx][ny]);
                visited[nx][ny] = false; // 백트래킹
            }
        }
    }

    // ㅗ 모양 (회전 및 대칭 포함) 처리
    private static void checkSpecialShape(int x, int y) {
        // ㅗ, ㅜ, ㅓ, ㅏ 모양 탐색
        int[][] shapes = {
                {0, 1, 0, -1, 1, 0},  // ㅗ
                {0, 1, 0, -1, -1, 0}, // ㅜ
                {-1, 0, 1, 0, 0, 1},  // ㅓ
                {-1, 0, 1, 0, 0, -1}  // ㅏ
        };

        for (int[] shape : shapes) {
            int sum = arr[x][y];
            boolean isValid = true;

            for (int i = 0; i < 3; i++) {
                int nx = x + shape[i * 2];
                int ny = y + shape[i * 2 + 1];

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) {
                    isValid = false;
                    break;
                }

                sum += arr[nx][ny];
            }

            if (isValid) {
                maxSum = Math.max(maxSum, sum);
            }
        }
    }
}