[백준][14500번]테트로미노[JAVA]

문제 설명

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

정사각형은 서로 겹치면 안 된다.
도형은 모두 연결되어 있어야 한다.
정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

풀이 방법

• 어떻게 풀어야되는지 많이 고민했던 문제였다.
• 하지만, 풀이를 찾아보니 ㅜ 모양을 제외한 나머지 블록이 dfs 탐색이랑 똑같다는 것이다 !!!
• 그래서 dfs를 통해 블럭들을 구했고, ㅜ는 따로 시뮬레이션을 통해 답을 얻을 수 있었다.

알아야되는 개념

• dfs
• 구현

import java.io.*;
import java.util.*;
public class Main {
    static int N,M;
    static int dx[] = {1,0,-1,0};
    static int dy[] = {0,1,0,-1};
    static boolean check[][] = new boolean[501][501];
    static int board[][] = new int[501][501];
    static int ans = Integer.MIN_VALUE;
    static void dfs(int depth, int x, int y, int sum){
        if(depth == 4){
            ans = Math.max(ans, sum);
            return ;
        }
        else {
            for(int i=0;i<4;i++){
                int nx = dx[i] + x;
                int ny = dy[i] + y;
                if(nx>=N || nx<0 || ny>=M || ny<0) continue;
                if(check[nx][ny]) continue;
                check[nx][ny] = true;
                dfs(depth + 1, nx, ny, sum + board[nx][ny]);
                check[nx][ny] = false;
            }
        }
    }
    static void init_check(){
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                check[i][j] = false;
            }
        }
    }
    static boolean point_check(int x, int y){
        if(x>=N || x<0 || y>=M || y<0) return false;
        return true;
    }
    static void last_check(int x, int y){
        if(point_check(x,y-1) && point_check(x,y) && point_check(x,y+1) && point_check(x+1,y)) {
            int sum = 0;
            sum = board[x][y-1] + board[x][y] + board[x][y+1] + board[x+1][y];
            ans = Math.max(sum ,ans);
        }
        if(point_check(x-1,y) && point_check(x,y) && point_check(x,y+1) && point_check(x+1,y)) {
            int sum = 0;
            sum = board[x-1][y] + board[x][y] + board[x][y+1] + board[x+1][y];
            ans = Math.max(sum ,ans);
        }
        if(point_check(x,y-1) && point_check(x,y) && point_check(x,y+1) && point_check(x-1,y)) {
            int sum = 0;
            sum = board[x][y-1] + board[x][y] + board[x][y+1] + board[x-1][y];
            ans = Math.max(sum ,ans);
        }
        if(point_check(x-1,y) && point_check(x,y) && point_check(x+1,y) && point_check(x,y-1)) {
            int sum = 0;
            sum = board[x-1][y] + board[x][y] + board[x+1][y] + board[x][y-1];
            ans = Math.max(sum ,ans);
        }
    }
    static void sol(){
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                check[i][j] = true;
               dfs(1,i,j,board[i][j]);
               last_check(i,j);
               init_check();
            }
        }
        System.out.println(ans);
    }

    public static void main(String[] args) throws IOException {
        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++){
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        sol();

    }
}