테트로미노

풀이

처음엔 모든 테트로미노의 모양을 배열에 저장해서 하나하나 비교하는 식으로 하려 했습니다. 회전과 대칭 모두 검사해야 하므로 배열을 만드는 것이 쉽지 않았습니다. 실수할 확률도 매우 높았습니다. 역시나 실수해서 이런 식으로 푸는 것은 매우 비효율적이고 도움이 안된다고 생각했습니다.
아래는 모든 모양을 구현한 배열로 문제를 해결하려 시도한 코드입니다.

import java.util.*;

public class Main {

    public static int N, M;
    public static int[][] paper;

    public static ArrayList<int[]> getTetoromino(int type, int direction, int[] point) {
        int[][][] dr = {{{0, 0, 0, 0}, {0, 1, 2, 3}, {0, 0, 0, 0}, {0, 1, 2, 3}, {0, 0, 0, 0}, {0, 1, 2, 3}, {0, 0, 0, 0}, {0, 1, 2, 3}},
                {{0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 1, 1}, {0, 0, 1, 1}},
                {{0, 1, 2, 2}, {0, 0, 0, 1}, {0, 0, 1, 2}, {1, 1, 1, 0}, {0, 1, 2, 2}, {0, 0, 0, 1}, {0, 0, 1, 2}, {0, 1, 1, 1}},
                {{0, 1, 1, 2}, {0, 0, 1, 1}, {0, 1, 1, 2}, {0, 0, 1, 1}, {0, 1, 1, 2}, {0, 0, 1, 1}, {0, 1, 1, 2}, {0, 0, 1, 1}},
                {{0, 0, 0, 1}, {0, 1, 1, 2}, {0, 1, 1, 1}, {0, 1, 1, 2}, {0, 0, 0, 1}, {0, 1, 1, 2}, {0, 1, 1, 1}, {0, 1, 1, 2}}};
        int[][][] dc = {{{0, 1, 2, 3}, {0, 0, 0, 0}, {0, 1, 2, 3}, {0, 0, 0, 0}, {0, 1, 2, 3}, {0, 0, 0, 0}, {0, 1, 2, 3}, {0, 0, 0, 0}},
                {{0, 1, 0, 1}, {0, 1, 0, 1}, {0, 1, 0, 1}, {0, 1, 0, 1}, {0, 1, 0, 1}, {0, 1, 0, 1}, {0, 1, 0, 1}, {0, 1, 0, 1}},
                {{0, 0, 0, 1}, {0, 1, 2, 0}, {0, 1, 1, 1}, {0, 1, 2, 2}, {1, 1, 0, 1}, {0, 1, 2, 2}, {0, 1, 0, 0}, {0, 0, 1, 2}},
                {{0, 0, 1, 1}, {1, 2, 0, 1}, {0, 0, 1, 1}, {1, 2, 0, 1}, {0, 0, 1, 1}, {1, 2, 0, 1}, {0, 0, 1, 1}, {1, 2, 0, 1}},
                {{0, 1, 2, 1}, {1, 0, 1, 1}, {1, 0, 1, 2}, {0, 0, 1, 0}, {0, 1, 2, 1}, {1, 0, 1, 1}, {1, 0, 1, 2}, {0, 0, 1, 0}}};
        ArrayList<int[]> result = new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            result.add(new int[]{point[0] + dr[type][direction][i], point[1] + dc[type][direction][i]});
        }
        return result;
    }

    public static boolean isRange(ArrayList<int[]> tetromino) {
        for (int[] point : tetromino) {
            if (!(0 <= point[0] && point[0] < N && 0 <= point[1] && point[1] < M)) return false;
        }
        return true;
    }

    public static int getScore(ArrayList<int[]> tetromino) {
        int result = 0;
        for (int[] point : tetromino) {
            result += paper[point[0]][point[1]];
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();
        paper = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                paper[i][j] = scanner.nextInt();
            }
        }
        int result = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                for (int type = 0; type < 5; type++) {
                    for (int direction = 0; direction < 8; direction++) {
                        ArrayList<int[]> tetromino = getTetoromino(type, direction, new int[]{i, j});
                        if (isRange(tetromino)) {
                            result = Math.max(result, getScore(tetromino));
                        }
                    }
                }
            }
        }
        System.out.println(result);
    }
}

배열의 하나만 잘못 만들어도 틀리고 찾기가 매우 힘듭니다. 그래서 다른 사람의 블로그를 참조했습니다. 제가 참조한 글은 이것입니다. 이 글을 보고 어떤 점에서 깊이가 3만큼 상하좌우로 이동하면 검사하길 원하는 테트로미노 4개의 회전, 반전된 모양을 모두 검사할 수 있다는 것을 알았습니다. 이 사실만 알면 문제를 해결하는 것은 어렵지 않습니다.

구현

import java.util.*;

public class Main {

    public static int N, M;
    public static int[][] paper;
    public static int result = Integer.MIN_VALUE;
    public static boolean[][] visited;
    public static int[] dr = {1, 0, -1, 0};
    public static int[] dc = {0, 1, 0, -1};

    // ㅗ모양을 제외한 다른 모양 모두 탐색
    public static void dfs(int row, int column, int sum, int depth) {
        if (depth == 3) {
            result = Math.max(result, sum);
            return;
        }
        visited[row][column] = true;
        for (int i = 0; i < 4; i++) {
            int nr = row + dr[i];
            int nc = column + dc[i];
            if (0 <= nr && nr < N && 0 <= nc && nc < M && !visited[nr][nc]) {
                dfs(nr, nc, sum + paper[nr][nc], depth + 1);
            }
        }
        visited[row][column] = false;
    }

    // ㅗ모양 탐색
    public static void exDfs(int row, int column) {
        int count = 0;
        int sum = paper[row][column];
        int[] dr = {0, 0, 1, -1};
        int[] dc = {-1, 1, 0, 0};
        for (int i = 0; i < 4; i++) {
            int nr = row + dr[i];
            int nc = column + dc[i];
            if (0 <= nr && nr < N && 0 <= nc && nc < M) {
                count++;
                sum += paper[nr][nc];
            }
        }
        if (count == 3)
            result = Math.max(result, sum);
        if (count == 4) {
            for (int i = 0; i < 4; i++) {
                sum -= paper[row + dr[i]][column + dc[i]];
                result = Math.max(result, sum);
                sum += paper[row + dr[i]][column + dc[i]];
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();
        paper = new int[N][M];
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                paper[i][j] = scanner.nextInt();
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                dfs(i, j, paper[i][j], 0);
                exDfs(i, j);
            }
        }
        System.out.println(result);
    }
}

깊이 우선 탐색을 통해 4개의 모양을 모두 탐색했고 ㅗ모양은 일단 십자가 모양의 합을 구한 뒤, 십자가의 각 튀어나온 부분을 한 개씩 빼서 비교했습니다.

시간 복잡도 분석

$dfs()$ 함수는 한 점에서 다음 점의 경우의 수를 한 깊이당 곱하면 호출 횟수를 알 수 있습니다. $4\times3\times3=36$이므로 상수입니다. $exDfs()$함수도 반복문이 최대 4번 반복하므로 상수입니다. 따라서 위 코드의 시간 복잡도는 $O(NM)$입니다.

회고

모든 테트로미노의 회전, 반전을 탐색하는 방법이 깊이가 3까지 깊이 우선 탐색을 하는 것이라는 사실을 모른다면 매우 어렵다고 생각합니다.