[백준 14500] 테트로미노 -Java

---

일단 모든 경우의 수를 찾아서 최대값을 구해야 하는 문제로
DFS로 풀어야 된다고 생각했다.

하지만 어떻게 접근할지 몰라서, 힌트를 참고 했다.
결론은 'ㅜ'외 나머지 도형은 재귀호출을 통해 모든 형태로 나타낼수 있다

즉, 시작지점부터 시작하여 상,하,좌,우를 살피면서 값이 있는 경우 재귀를 호출하고 이렇게 4번 호출이 되면 4개의 정수를 합산한 값을 구하면 된다.

그리고 'ㅜ' 도형의 경우는 상,하,좌,우 살피면서 값이 있는 경우 합산하되 상,하,좌,우 모두 값이 있는 경우 최종적으로 가장 낮은 값을 빼주면 된다.

아래의 코드로 구현했다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {

	static int result = Integer.MIN_VALUE;
	static int N;
	static int M;
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, -1, 0, 1};
	static int[][] irr;
	static boolean[][] visited;
	
	static void dfs(int y, int x, int cnt, int pos) {
    	// 도형이 완성되면 최대값 구하고 리턴
		if(cnt == 4) {
			result = Math.max(result, pos);
			return;
		}
		
		for(int i = 0; i < 4; i++) {
			int nexti = y + dy[i];
			int nextj = x + dx[i];
			
            // 종이 범위에 벗어나면 다음 방향 진행
			if(nexti < 0 || nextj < 0 || nexti >= N || nextj >= M) {
				continue;
			}
            
            // 현재 방문한 위치인지 확인
			if(visited[nexti][nextj]) {
				continue;
			}

			visited[nexti][nextj] = true;
			dfs(nexti, nextj, cnt +1, pos + irr[nexti][nextj]);
			visited[nexti][nextj] = false;
		}
		
	}
	
    // 'ㅜ'도형에서 최대값 구하기
	static void excep(int y, int x) {
    	// wing은 상,하,좌,우
		int wing = 4;
		int min = Integer.MAX_VALUE;
		int sum = irr[y][x];
		
		for(int i = 0; i < 4; i++) {
			int nexti = y + dy[i];
			int nextj = x + dx[i];
			
            // wing이 2개이하면 'ㅜ'도형이 아님
			if(wing <= 2) {
				return;
			}
			
            // 종이 범위에 벗어난 경우 잘린 도형 확인
			if(nexti < 0 || nextj < 0 || nexti >= N || nextj >= M) {
				wing--;
				continue;
			}
			
			min = Math.min(min, irr[nexti][nextj]);
			sum = sum + irr[nexti][nextj];
		}

		// 상,하,좌,우 모두 값 있을시, 그 중 최소값을 뺴준다
		if(wing == 4) {
			sum = sum - min;
		}
		result = Math.max(result, sum);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		String[] arr = str.split(" ");
		
		N = Integer.parseInt(arr[0]);
		M = Integer.parseInt(arr[1]);
		
		irr = new int[N][M];
		visited = new boolean[N][M];

		for(int i = 0; i < N; i++) {
			String[] nrr = br.readLine().split(" ");
			for(int j = 0; j < M; j++) {
				irr[i][j] = Integer.parseInt(nrr[j]); 
			}
		}

		// 종이판 (0,0) 부터 탐색 시작
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				dfs(i, j, 0, 0);
				excep(i, j);
			}
		}
		System.out.print(result);
		
	}
 
}