문제

풀이

이해

주어진 2차원 공간에 테트로미노 도형을 배치한다.

2차원 공간에는 각각 정수가 주어지는데 이 때 테트로미노가 가지는 정수의 합의 최대를 구하는 문제이다.

접근

본 문제는 아래 포스팅을 참고하여 풀이하였다.
링크텍스트

2차원 공간은 임의의 수를 입력받는다. 테트로미노는 임의의 수가 들어있는 공간에 배치되기 때문에 미리 어떤식으로 배치되어야 합의 최대가 될 수 있는지는 알 수 없다.

따라서, 모든 경우에 대해 완전탐색을 할 필요가 있어 보인다.

그렇다면 완전 탐색은 어떻게 할까?

일단, N x M 공간에서 하나씩 기준을 잡아 탐색해야 한다.

첫번째 생각한 방법은 기준점에 대하여 가질 수 있는 모든 도형의 방향값을 나타내는 배열을 생성하는 것이다.

하지만, 이 방법은 모든 도형에 대한 경우를 배열로 생성해야 하기 때문에 시간복잡도가 매우 커질것으로 예상된다.

두번째 방법은 기준점부터 시작하여 포함할 수 있는 블록을 차례로 선택하여 테트로미노를 완성하는 것이다.

이 방법은 기준점에 대해 DFS를 수행하여 인접 블록을 선택하면 된다.

하지만 위 도형은 DFS로 선택될 수 없다. 따라서, 이 도형에 대한 처리만 따로 하면 된다.

코드

package java_baekjoon;

import java.util.Scanner;

public class prob14500 {
    static int N;
    static int M;
    static int[][] arr;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int ans = 0;
    public static void main(String[] args){
        Scanner sc= new Scanner(System.in);

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

        arr = new int[N][M];
        visited = new boolean[N][M];
        
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                arr[i][j] = sc.nextInt();
            }
        }

        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                visited[i][j] = true;
                DFS(i, j, arr[i][j], 1);

                visited[i][j] = false;

                remain(i, j, arr[i][j], 1);
            }
        }

        System.out.println(ans);
        sc.close();
        return;
    }
    public static void DFS(int row, int col, int sum, int cnt){
        if(cnt == 4){
            ans = Math.max(ans, sum);
            return;
        }

        for(int i=0;i<4;i++){
            int cur_row = row + dx[i];
            int cur_col = col + dy[i];

            if(cur_row < 0 || cur_row >= N || cur_col < 0 || cur_col >= M){
                continue;
            }

            if(!visited[cur_row][cur_col]){
                visited[cur_row][cur_col] = true;
                DFS(cur_row, cur_col, sum + arr[cur_row][cur_col], cnt+1);
                visited[cur_row][cur_col] = false;
            }
        }
    }
    public static void remain(int row, int col, int sum, int cnt){
        if(cnt == 4){
            ans = Math.max(ans, sum);
            return;
        }

        for(int i=0;i<4;i++){
            int cur_row = row + dx[i];
            int cur_col = col + dy[i];

            if(cur_row < 0 || cur_row >= N || cur_col < 0 || cur_col >= M){
                continue;
            }

            if(!visited[cur_row][cur_col]){
                visited[cur_row][cur_col] = true;
                remain(row, col, sum + arr[cur_row][cur_col], cnt+1);
                visited[cur_row][cur_col] = false;
            }
        }
    }
}

결과