[JAVA] 백준 테트로미노

DFS를 활용한 문제이다.

하지만 DFS를 숨겨놓아서 알아내기 어려운 문제였다.

 

 

블로그출처 

https://velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-14500-%ED%85%8C%ED%8A%B8%EB%A1%9C%EB%AF%B8%EB%85%B8#dfs%EB%A5%BC-%EC%82%AC%EC%9A%A9%ED%95%B4%EC%84%9C-%ED%95%A9%EC%9D%98-%EC%B5%9C%EB%8C%93%EA%B0%92%EC%9D%84-%EA%B5%AC%ED%95%98%EB%8A%94-%EB%AC%B8%EC%A0%9C-%E3%85%9C-%EB%AA%A8%EC%96%91%EC%9D%80-%EC%98%88%EC%99%B8%EC%B2%98%EB%A6%AC-%ED%95%A9%EB%8B%88%EB%8B%A4

백준 14500 테트로미노

 

 

위 모양들을 조합해보자

처음에는 각각의 모양들을 대칭,회전 시켜서 그에 맞는 틀에 끼워넣는것에 대해 골머리를 앓았다.

하지만 'ㅜ'모양을 제외한 것들은 depth=4인 dfs의 집합체이다.

흰색부분에서 출발해서, depth=4인부분까지 경우의수.

따라서 'ㅜ'모양을 제외한 모양은 DFS실행으로 모두 탐색이되고, 그러므로 'ㅜ'모양은 따로 탐색해주어야한다.

'ㅜ'모양

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

/*
    시간 복잡도: O(n^2)
    공간 복잡도: O(n^2)
    사용한 알고리즘: 백트래킹 (DFS)
    사용한 자료구조: 2차원 배열
 */

public class Main {

    private static int n, m, a[][], result;
    private static Boolean check[][];
    private static int dx[] = {0, 0, 1, -1};
    private static int dy[] = {-1, 1, 0, 0};

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

        // 1. 입력
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        a = new int[n+1][m+1];
        check = new Boolean[n+1][m+1];
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                check[i][j] = false;
            }
        }

        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=m; j++){
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // 2. 계산
        // 2. 2차원 배열 각각의 원소에서 검사를 수행합니다.
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                // 1) DFS 로 검사

                // 방문했던 점을 또 방문해야하기 때문에
                // 들어가기전 체크를 해주고, 끝났을때 체크를 해제해줍니다.
                check[i][j] = true;

                dfs(i, j, a[i][j], 1);

                // 체크를 해제하면 무한루프에 들어가 않을까 걱정할 수 있습니다.
                // 길이로 재귀를 중단시키기 때문에, 수행횟수는 4 * 3 * 3, 한점에서 최대 36번 수행됩니다.
                check[i][j] = false;

                // 2) ㅏ 모양 검사
                check_exshape(i, j);
            }
        }

        // 3. 출력
        System.out.println(result);
    }



    // DFS 로 4가지 모양 검사 (ㅜ 제외)
    public static void dfs(int x, int y, int sum_value, int length){
        // 길이가 4 이상이면 종료해줍니다.
        if(length >= 4){
            result = Math.max(result, sum_value);
            return;
        }

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

            // 지도 넘어가는 경우 검사
            if(nx < 1 || nx > n || ny < 1 || ny > m) continue;

            // 방문하지 않은 점이면
            if(check[nx][ny] == false) {

                // 들어가기전 체크해주고
                check[nx][ny] = true;

                dfs(nx, ny, sum_value + a[nx][ny], length + 1);
                // 하나의 탐색을 완료하면 여기로 돌아옵니다.

                // 나올때 체크를 해제합니다.
                check[nx][ny] = false;
            }
        }
    }

    // ㅜ 모양 검사
    public static void check_exshape(int x, int y){
        int sum_value = 0;
        // 1. ㅜ
        if(x>=1 && x+1<=n && y>=1 && y+2<=m){
            sum_value = a[x][y] + a[x][y+1] + a[x][y+2] + a[x+1][y+1];
            result = Math.max(result, sum_value);
        }

        // 2. ㅏ
        if(x >= 1 && x+2 <=n && y>=1 && y+1<=m){
            sum_value = a[x][y] + a[x+1][y] + a[x+2][y] + a[x+1][y+1];
            result = Math.max(result, sum_value);
        }

        // 3. ㅗ
        if(x-1 >= 1&& x <=n && y >=1 && y+2 <=m){
            sum_value = a[x][y] + a[x][y+1] + a[x][y+2] + a[x-1][y+1];
            result = Math.max(result, sum_value);
        }

        // 4. ㅓ
        if(x-1 >= 1 && x+1 <=n && y >=1 && y+1 <=m){
            sum_value = a[x][y] + a[x][y+1] + a[x-1][y+1] + a[x+1][y+1];
            result = Math.max(result, sum_value);
        }
    }
}