https://www.acmicpc.net/problem/14500

테트로 미노

풀이

처음에는 각각의 모향을 직접 구현하여 회전, 대칭을 통해 전체 경우의 수를 탐색하려고 했다.

그런데 그렇게 하자니 너무 귀찮았다.

그래서 구글에 검색을 했더니 dfs를 통해 'ㅗ' 모양을 제외한 다른 4개의 모양은 dfs로 구할 수 있다는 사실을 알았다.

그래서 dfs로 4개의 모양의 경우의 수를 구했고, 'ㅗ'만 따로 메소드를 작성하여 정답을 구했다.

주의해야할 점은 dfs로 4개의 모양을 구할 때 갔던 지점을 다시 방문해야 하기때문에 depth 4까지 탐색이 끝나고 나면 이전에 방문했던 지점을 다시 방문할 수 있게 처리해줘야 한다.

코드

import java.io.*;

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int ans = 0;
    static int n, m;
    static boolean[][] visit;
    static int[][] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] first = br.readLine().split(" ");
        n = Integer.parseInt(first[0]);
        m = Integer.parseInt(first[1]);
        graph = new int[n][m];
        visit = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(line[j]);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visit[i][j] = true;
                dfs(i, j, 0, 0);
                visit[i][j] = false;
                other(i,j);
            }
        }
        bw.write(ans + "\n");
        br.close();
        bw.close();
    }

    private static void dfs(int x, int y, int cnt, int sum) {
        if (cnt == 4) {
            ans = Math.max(ans, sum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            if ((x + dx[i] >= 0 && x + dx[i] <= n - 1)
                    && (y + dy[i] >= 0 && y + dy[i] <= m - 1)) {
                if (!visit[x + dx[i]][y + dy[i]]) {
                    visit[x + dx[i]][y + dy[i]] = true;
                    dfs(x + dx[i], y + dy[i], cnt + 1, sum + graph[x + dx[i]][y + dy[i]]);
                    visit[x + dx[i]][y + dy[i]] = false;
                }
            }
        }
    }

    private static void other(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int sum = 0;
            // ㅜ
            if (x >= 0 && x + 1 <= n - 1 && y >= 0 && y + 2 <= m - 1) {
                sum = graph[x][y] + graph[x][y + 1] + graph[x][y + 2] + graph[x + 1][y + 1];
                ans = Math.max(ans, sum);
            }
            // ㅏ
            if (x >= 0 && x + 2 <= n - 1 && y >= 0 && y + 1 <= m - 1) {
                sum = graph[x][y] + graph[x + 1][y] + graph[x + 2][y] + graph[x + 1][y + 1];
                ans = Math.max(ans, sum);
            }
            // ㅓ
            if (x >= 0 && x + 2 <= n - 1 && y - 1 >= 0 && y + 1 <= m - 1) {
                sum = graph[x][y] + graph[x + 1][y] + graph[x + 2][y] + graph[x + 1][y - 1];
                ans = Math.max(ans, sum);
            }
            // ㅗ
            if (x - 1>= 0 && x + 1 <= n - 1 && y >= 0 && y + 2 <= m - 1) {
                sum = graph[x][y] + graph[x][y + 1] + graph[x][y + 2] + graph[x - 1][y + 1];
                ans = Math.max(ans, sum);
            }
        }
    }
}