[백준] 14500 - 테트로미노 [JAVA]

 

 

코드

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

public class Main {

    static int max = Integer.MIN_VALUE;
    static int N, M;
    static int[][] board;
    static boolean[][] visit; // 방문 체크 배열
    // 상하좌우
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        board = new int[N][M];
        visit = new boolean[N][M];

        // 입력값
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < M; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visit[i][j] = true;
                DFS(i, j, board[i][j], 1);
                visit[i][j] = false;
            }
        }

        System.out.println(max);
    }

    static void DFS(int x, int y, int sum, int count) {

        // 테트로미노 완성 시 수들의 합 계산
        if (count == 4) {
            max = Math.max(max, sum);
            return;
        }

        // 상하좌우 탐색
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i]; // 다음 탐색 행
            int ny = y + dy[i]; // 다음 탐색 열

            // 범위 벗어나는 경우
            if (0 > nx || N <= nx || 0 > ny || M <= ny) {
                continue;
            }

            if (!visit[nx][ny]) { // 방문하지 않은 곳이라면

                // (ㅗ) 형태 만들기 위해 두 번째 칸에서 탐색 한번 더 진행
                if (count == 2) {
                    visit[nx][ny] = true;
                    DFS(x, y, sum + board[nx][ny], count + 1);
                    visit[nx][ny] = false;
                }

                visit[nx][ny] = true; // 방문 체크
                DFS(nx, ny, sum + board[nx][ny], count + 1);
                visit[nx][ny] = false;
            }
        }
    }

}