[백준 14500] 테트로미노(Java)

문제 링크 : https://www.acmicpc.net/problem/14500

이 문제는 백트래킹을 사용하여 풀 수 있습니다.

문제의 특징을 잘 살펴보면, 4개의 블록을 만들 수 있는 경우의 수는 특정 시작점으로부터 4칸 연속으로 이동하는 경우의 수와 같습니다. 따라서 백트래킹으로 현재 위치에서 상하좌우 1칸씩 이동해가면서 4칸이 되었을 때 합의 최댓값을 비교하면 됩니다.

여기서 주의할 점은, 'ㅗ'모양 블록은 위의 경우에 포함되지 않는다는 것입니다. 따라서 이 부분은 직접 수작업으로 처리해주어야 합니다. 크게 ㅗ,ㅏ,ㅜ,ㅓ 모양이 존재하기 때문에, 기준점을 잡아 나머지 블록의 좌표를 구한 후 직접 더해서 비교하시면 됩니다. 이 때 모든 수가 + 연산만 진행하도록 하는 것이 조건을 하나 덜 작성해도 되므로 더 유리합니다. 왜냐하면 기본적으로 반복문에서 맵의 범위까지는 선택하기 때문에 - 연산이 들어가게 될 경우 시작점 위치도 조건을 주어야 하지만 + 연산이 들어가게 될 경우 시작점 위치는 맵의 범위 내에 존재하기 때문에 굳이 설정하지 않아도 되기 때문입니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

public class Main{

    static int N,M;
    static int res = 0;
    static int[][] req = new int[501][501];
    static boolean[][] check = new boolean[501][501];
    static int[] dx = {1,0,-1,0};
    static int[] dy = {0,1,0,-1};

    static void backtracking(int y, int x, int cnt, int sum){
        if(cnt==4) {
            if(res<sum) res = sum;
            return;
        }

        for(int i=0;i<4;i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || nx>=M || ny<0 || ny>=N) continue;

            if(!check[ny][nx]){
                check[ny][nx] = true;
                backtracking(ny,nx,cnt+1,sum+req[ny][nx]);
                check[ny][nx] = false;
            }
        }
    }

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

        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++){
                check[i][j] = true;
                req[i][j] = Integer.parseInt(st.nextToken());
                check[i][j] = false;
            }
        }

        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                check[i][j] = true;
                backtracking(i,j,1,req[i][j]);
                check[i][j] = false;

                // 현재 위치에서 ㅗ 모양 블록 가능한 경우의 수 일일히 추가

                // case 1. ㅗ
                // 맨 위 기준 (x,y), (x-1,y+1), (x,y+1), (x+1,y+1)
                if(j+2<M && i+1<N){
                    int sum = req[i][j+1] + req[i+1][j] + req[i+1][j+1] + req[i+1][j+2];
                    if(res<sum) res = sum;
                }

                // case 2. ㅏ
                // 맨 위 기준 (x,y), (x,y+1), (x,y+2), (x+1,y+1)
                if(j+1<M && i+2<N){
                    int sum = req[i][j] + req[i+1][j] + req[i+2][j] + req[i+1][j+1];
                    if(res<sum) res = sum;
                }

                // case 3. ㅜ
                // 맨 위 왼쪽 기준 (x,y), (x+1,y), (x+2,y), (x+1,y+1)
                if(j+2<M && i+1<N){
                    int sum = req[i][j] + req[i][j+1] + req[i][j+2] + req[i+1][j+1];
                    if(res<sum) res = sum;
                }

                // case 4. ㅓ
                // 맨 위 기준 (x,y), (x-1,y+1), (x,y+1), (x,y+2)
                if(j+1<M && i+2<N){
                    int sum = req[i][j+1] + req[i+1][j] + req[i+1][j+1] + req[i+2][j+1];
                    if(res<sum) res = sum;
                }

            }
        }

        System.out.println(res);
    }
}