이번에 풀어본 문제는
백준 14500번 테트로미노 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static int [][] map;
    static int [] dx = {0,0,1,-1};
    static int [] dy = {1,-1,0,0};
    static int [][] ex = {{0,0,-1},{0,0,1},{0,-1,1},{-1,1,0}}; // ㅗ ㅜ ㅓ ㅏ
    static int [][] ey = {{-1,1,0},{-1,1,0},{-1,0,0},{0,0,1}};
    static boolean [][] isVis;
    static int n,m;
    static int maxVal = Integer.MIN_VALUE;

    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());
        map = new int[n][m];

        for(int i = 0; i < n; ++i)
        {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; ++j)
            {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        isVis = new boolean[n][m];
        for(int i = 0; i < n; ++i)
        {
            for(int j = 0; j < m; ++j)
            {
                isVis[i][j] = true;
                dfs(i,j,1,map[i][j]);
                isVis[i][j] = false;
                getElse(i,j);
            }
        }
        System.out.print(maxVal);
    }
    static void dfs(int x, int y,int cnt,int val)
    {
        if(cnt == 4)
        {
            maxVal = Math.max(maxVal,val);
            return;
        }
        for(int idx = 0; idx < 4; ++idx)
        {
            int mx = x + dx[idx];
            int my = y + dy[idx];

            if(!isValid(mx,my) || isVis[mx][my]) continue;
            isVis[mx][my] = true;
            dfs(mx,my,cnt+1,val+map[mx][my]);
            isVis[mx][my] = false;
        }
    }
    static boolean isValid(int x, int y)
    {
        return x >= 0 && y >= 0 && x < n && y < m;
    }
    static void getElse(int x, int y)
    {
        next : for(int i = 0; i < 4; ++i)
        {
            int res = map[x][y];
            for(int j = 0; j < 3; ++j)
            {
                int mx = x + ex[i][j];
                int my = y + ey[i][j];

                if(!isValid(mx,my)) continue next;
                res += map[mx][my];
            }
            maxVal = Math.max(maxVal,res);
        }
    }
}

📝 풀이

먼저 dfs로 풀이를 해보았지만 (ㅗ,ㅜ,ㅓ,ㅏ) 모양은 dfs로 탐색이 불가능하기 때문에, 별도로 해당 모양을 탐색할 2차원 배열을 만들어서 추가적으로 탐색해주었습니다.
흔한 dfs문제와 흐름이 같고, getElse 함수로 모양을 만들 수 있을경우 추가적으로 최댓값을 비교하여 갱신해주도록 합니다.

📜 후기

이전에 풀었던 칠공주 문제처럼 조합을 이용할까 했지만, 최대 크기가 500이라서
25000개중에 4개를 택하는 모든 조합을 구하면.... 안되겠더라구요ㅋㅋㅋㅋㅋ
처음에 dfs를 돌기 전마다 방문배열을 초기화해줬더니 시간초과 떴습니다;
평소 초기화 위치는 크게 신경 안썼었는데, 이번에 대체 왜??! 하며 곰곰히 찾다보니 사소하게 넘어갔던 부분에서 또 하나 배워갑니다!
월급 루팡중인 동기가 골라준 문제인데,뭔가 알록달록 접근부터 흥미로운 문제였습니다 😀ㄱㅅ