[전체 코드]

// 테트로미노
package graphSearh;
import java.util.*;

public class BJ14500 {
    static int n, m;
    static int maxSum = 0;
    static boolean[][] visited;
    static int[][] board;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        board = new int[n][m];
        visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                board[i][j] = sc.nextInt();
            }
        }

        // 함수 호출
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visited[i][j] = true; 
                solve(1, board[i][j], i, j);
                visited[i][j] = false;
            }
        }
        System.out.println(maxSum);
    }

    public static void solve(int depth, int sum, int x, int y) {
        if (depth == 4) {
            maxSum = Math.max(sum, maxSum);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (!visited[nx][ny]) {
                    // ㅗ, ㅜ, ㅏ, ㅓ 예외처리를 하는 코드가 필요
                    if (depth == 2) {
                        visited[nx][ny] = true;
                        solve(depth + 1, sum + board[nx][ny], x, y); // depth와 sum은 갱신, 좌표는 이동 x
                        visited[nx][ny] = false;
                        // return을 하지 않은 이유: 다른 모양도 봐야하기 때문.
                    }
                    // 그 외 다른 모양을 위한 코드
                    visited[nx][ny] = true;
                    solve(depth + 1, sum + board[nx][ny], nx, ny);
                    visited[nx][ny] = false;
                }
            }
        }
    }
}

[문제 풀이 설명]

문제는, 주어진 종이 위에 테트로미노를 놓을 수 있는 모든 경우의 수 중에서, 놓은 수의 합이 최대일 경우를 구하는 문제이다.

즉! 모든 경우의 수로 테트로미노를 놓아야 하므로 위 문제는 백트래킹을 사용하여 모든 경우를 보면 된다.

일단, 테트로미노는 크기가 4인 정사각형으로 모양은 다양하다.
백트래킹으로 탐색하면서 depth(크기)가 4가 되면 해당 칸들의 합을 구하면 된다.

그런데 여기서 예외사항이 있다.
ㅗ, ㅜ, ㅓ, ㅏ 인 경우가 예외사항인데,

왼쪽 도형을 예로 들면, depth이 1부터 시작해서 4가 되면 테트로미노를 완성한다. 그러나, 오른쪽 도형을 보면, 저 도형을 탐색하기 위해서는 depth가 5(4 + 1)가 되는 것이다.

따라서, depth가 2일 때 예외처리하는 코드가 필요하다.

if (depth == 2) {
	visited[nx][ny] = true;
	solve(depth + 1, sum + board[nx][ny], x, y); // depth와 sum은 갱신, 좌표는 이동 x
	visited[nx][ny] = false;
	// return을 하지 않은 이유: 다른 모양도 봐야하기 때문.
}

위 코드처럼, depth가 2일 때 ㅗ, ㅜ, ㅓ, ㅏ 경로로 가기 위해서 재귀 호출을 할 때, depth와 sum은 갱신해주고 이동할 좌표는 새로운 좌표인 nx, ny가 아닌 x, y를 넣어서 좌표를 이동시키지 않게 하면 된다.
그러면 depth가 2일 때, 각각 동서남북으로 이동하는 척만 하면서 ㅗ, ㅜ, ㅓ, ㅏ인 경우를 모두 확인할 수 있게 된다.

[어려웠던 점]

문제 이해는 어렵지 않았지만, ㅗ, ㅜ, ㅓ, ㅏ를 처리하는 부분이 어려웠다.
아직 재귀 개념이 부족해서 그런가... 멍청해서 그런가..

그리고 if문 끝에 return을 적어주면 안 된다.
이유는, depth가 2일 때 ㅗ, ㅜ, ㅓ, ㅏ 모양 말고도 다른 모양을 더 봐야하는데 return을 해버리면 ㅗ, ㅜ, ㅓ, ㅏ 모양만 보는 거기 때문이다.

[느낀점]

어떤 상황을 예외처리를 해야할지 빠르게 생각해내자.
그리고 return을 무작정 적지 말고, 생각하고 적기.