[BaekJoon] 14500 테트로미노 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static final int[] DX = {-1, 1, 0, 0}, DY = {0, 0, -1, 1};
    static int N, M, max;
    static int[][] map;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        M = scanner.nextInt();
        map = new int[N][M];
        max = Integer.MIN_VALUE;

        for(int row = 0; row < N; row++) {
            for(int col = 0; col < M; col++)
                map[row][col] = scanner.nextInt();
        }
    }

	// ㅜ 모양의 테트로미노를 제외한 나머지 4개의 테트로미노를 한 위치에 회전하거나 대칭시켜 놓는다면
    // 한 위치에서 상하좌우로 DFS를 통해 이동할 수 있는 모든 경로가 나타난다
    // 그렇기 때문에 DFS를 통해 칸에 쓰인 수들의 합 중 최댓값을 구한다
    // ㅜ 모양의 테트로미노는 DFS를 통해 확인이 불가능하기 때문에 따로 케이스를 만들어 검사한다
    static void solution() {
        boolean[][] visited = new boolean[N][M];
        for(int row = 0; row < N; row++) {
            for(int col = 0; col < M; col++) {
                visited[row][col] = true;
                dfs(row, col, 1, map[row][col], visited);
                visited[row][col] = false;
                checkOtherCase(row, col);
            }
        }

        System.out.println(max);
    }

    static void checkOtherCase(int x, int y) {
        if(x < N - 2 && y < M - 1)
            max = Math.max(max, map[x][y] + map[x + 1][y] + map[x + 2][y] + map[x + 1][y + 1]);
        if(x < N - 2 && y > 0)
            max = Math.max(max, map[x][y] + map[x + 1][y] + map[x + 2][y] + map[x + 1][y - 1]);
        if(x < N - 1 && y < M - 2)
            max = Math.max(max, map[x][y] + map[x][y + 1] + map[x][y + 2] + map[x + 1][y + 1]);
        if(x > 0 && y < M - 2)
            max = Math.max(max, map[x][y] + map[x][y + 1] + map[x][y + 2] + map[x - 1][y + 1]);
    }

    static void dfs(int x, int y, int count, int sum, boolean[][] visited) {
        if(count >= 4) {
            max = Math.max(max, sum);
            return;
        }

        for(int dir = 0; dir < DX.length; dir++) {
            int cx = x + DX[dir], cy = y + DY[dir];

            if(isInMap(cx, cy) && !visited[cx][cy]) {
                visited[cx][cy] = true;
                dfs(cx, cy, count + 1, sum + map[cx][cy], visited);
                visited[cx][cy] = false;
            }
        }
    }

    static boolean isInMap(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < M;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}