[DFS및예외처리]백준_테트로미노

문제를 처음에 읽을 때는 시뮬레이션 문제인가 ..? 했었다.

먼저 입력포맷대로 코딩을 했다. 그리고 최대값을 구하는 문제라는 것을 보고 완전탐색으로 먼저 생각해보면서

최적화를 시켜보자라고 생각을 하였고 도형을 놓는 경우를 전부 다 따져보자하면서 생각을 해본 결과

 

도형의 대부분이 길이가 4인 dfs라는 것을 깨닫고 dfs문제 구나 !! 생각했다.

그 후, 뒤늦게 안 사실은 ㅏ,ㅓ,ㅜ,ㅗ 모양의 블록은 dfs로 탐색할 수 없다는 것(예외블록)을 알았다.

 

그리고 확인해본 결과 2차 배열의 각 모든 점에대해서 dfs를 따져서 최대값을 비교해야 한다는 것을 깨달았다.

한가지 배운 사실은 isV=True --> dfs --> isV=false 형식으로 해당 값에서만 isV유지하고 끝나면 다시 false로 초기화

시켜주는 과정이었다.

 

그리고 4방향으로 탐색을 해주는 방법은 하두 많이 나와서..

 

먼저 dfs 부분은 위와 같이 코딩했다. 이 부분은 많은 문제와 비슷한 포맷. 파라미터로 sum 변수를 쭉 가지고 들어가서

ans와 비교 후 최대 값을 저장해주는 방식. 

 

static int [][]Map;
    static boolean [][]isV;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1}; // 상 , 하, 좌 , 우
    static int N,M;
    static int ans=-1;
    
    public static void dfs(int x,int y,int len,int sum) {
        if(len == 4) {
            ans = Math.max(ans, sum);
            return ;
        }
        
        for(int i=0;i<4;i++) {
            int XX = x +dx[i];
            int YY = y + dy[i];
            if(0<=XX && XX < N && YY>=0 && YY < M) {
                if(isV[XX][YY] == false) {
                    isV[XX][YY] = true;
                    dfs(XX,YY,len+1,sum+Map[XX][YY]);
                    isV[XX][YY]=false;
                }
            }
            
        }
        
    }

예외 도형에 대해서는 다양한 인터넷의 방법들이 있었지만, 나만의 방법을 생각해보기로 했고, 각 점마다

ㅏ,ㅓ,ㅜ,ㅗ 를 전부 따져 주자고 생각하였고 범위 검사만 해주면 되겠다고 생각했다.

 

 

import java.util.*;
 
public class Main {
    
    static int [][]Map;
    static boolean [][]isV;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1}; // 상 , 하, 좌 , 우
    static int N,M;
    static int ans=-1;
    
    public static void dfs(int x,int y,int len,int sum) {
        if(len == 4) {
            ans = Math.max(ans, sum);
            return ;
        }
        
        for(int i=0;i<4;i++) {
            int XX = x +dx[i];
            int YY = y + dy[i];
            if(0<=XX && XX < N && YY>=0 && YY < M) {
                if(isV[XX][YY] == false) {
                    isV[XX][YY] = true;
                    dfs(XX,YY,len+1,sum+Map[XX][YY]);
                    isV[XX][YY]=false;
                }
            }
            
        }
        
    }
    
    public static void PLUS(int i, int j) {
        //ㅏ
        if(i-1 >= 0 && j+1 < M && i+1 < N) {
            ans=Math.max(ans, Map[i][j]+Map[i-1][j]+Map[i][j+1]+Map[i+1][j]);
        }
        //ㅜ
        if(j-1 >= 0 && i+1 < N && j+1 < M) {
            ans=Math.max(ans, Map[i][j]+Map[i][j-1]+Map[i+1][j]+Map[i][j+1]);
        }
        //ㅓ
        if(j-1>=0 && i-1 >=0 && i+1 < N) {
            ans=Math.max(ans, Map[i][j]+Map[i][j-1]+Map[i-1][j]+Map[i+1][j]);
        }
        //ㅗ
        if(j-1>=0 && i-1>=0 && j+1 < M) {
            ans=Math.max(ans, Map[i][j]+Map[i][j-1]+Map[i-1][j]+Map[i][j+1]);
        }
    }
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        Map = new int[N][M];
        isV = new boolean[N][M];
        
        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++){
                Map[i][j]=sc.nextInt();
            }
        }
        
        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++) {
                isV[i][j]=true;
                dfs(i,j,1,Map[i][j]);
                PLUS(i,j);
                isV[i][j]=false;
            }
        }
        
        System.out.println(ans);
    }
}