백준 14500 - 테트로미노

DFS + 시뮬레이션

ㅗ 모양을 예외처리 하는 것이 필요

import java.util.Scanner;

public class Main {
    static int N, M;
    static int map[][];
    static boolean visited[][];
    static int[] dx = {0,  0, -1, 1};
    static int[] dy = {-1, 1, 0, 0,};
    static int sum = 0;
    static int result = 0;
    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        map = new int[N+1][M+1];
        visited = new boolean[N+1][M+1];

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


        for(int i=1; i<N+1; i++){
            for(int j=1; j<M+1; j++){
                visited[i][j] = true;
                sum += map[i][j];
                dfs(i,j,1, sum);
                sum -= map[i][j];
                visited[i][j] = false;
            }
        }

        for(int i=1; i<N+1; i++){ // ㅗ 모양
            for(int j=1; j<M+1; j++){
                if(i-1>=1 && j-1 >= 1 && j+1 <= M){  // if(i-1>=1 && j-1 >= 1 && i+1<=N && j+1 <= M)
                    sum = map[i][j] + map[i-1][j] + map[i][j-1] + map[i][j+1];
                    if(sum > result)
                        result = sum;
                }
            }
        }

        for(int i=1; i<N+1; i++){ // ㅜ
            for(int j=1; j<M+1; j++){
                if(i-1 >= 0 && i <= N - 1 && j <= M - 1){
                    sum = map[i][j] + map[i][j-1] + map[i][j+1] + map[i+1][j];
                    if(sum > result)
                        result =sum;
                }
            }
        }

        for(int i=1; i<N+1; i++){ // ㅏ
            for(int j=1; j<M+1; j++){
                if(i-1 >= 1 && i <= N - 1 && j <= M - 1){
                    sum = map[i][j] + map[i-1][j] + map[i+1][j] + map[i][j+1];
                    if(sum > result)
                        result = sum;
                }
            }
        }
        
        for(int i=1; i<N+1; i++){ // ㅓ
            for(int j=1; j<M+1; j++){
                if(i-1 >= 1 && i <= N - 1 && j-1 >= 1){ 
                    sum = map[i][j] + map[i][j-1] + map[i+1][j] + map[i-1][j];
                    if(sum > result)
                        result =sum;
                }
            }
        }
        System.out.println(result);
    }

    static void dfs(int x, int y, int depth, int hap){

        if(depth == 4){
            if(hap > result)
                result = hap;
            return;
        }

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

            if(nx>=1 && ny>= 1 && nx <= N && ny <= M){
                if(visited[nx][ny] == false){
                    visited[nx][ny] = true;
                    hap += map[nx][ny];
                    dfs(nx,ny,depth+1, hap);
                    hap -= map[nx][ny];
                    visited[nx][ny] = false;
                }
            }
        }


    }

}