테트로미노

📍 문제 설명

 

💡 접근

DFS를 이용해서 'ㅗ' 모양의 테트로미노를 제외하고 나머지 테트로미노의 합을 구할 수 있다.

방문처리된 곳은 다시 방문하지 않으므로 'ㅗ' 모양의 테트로미노의 합을 구하는 부분은 따로 구해줘야한다.

1.모든 좌표에서 ㅡ,ㅁ,ㄱ,ㄱㅡ 모양의 합을 DFS로 구하기

2.모든 좌표에서 'ㅗ' 모양의 합을 '+' 의 합을 구하는 것 처럼 구하기

- 좌표를 벗어나면 cnt 갯수 줄이고 3개면 그대로 합을 구하고 4개면 최솟값을 빼서 합을 구한다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, answer, cnt, min;
    static String a, t;
    static int[][] board,clone;
    static boolean[] arr;
    static boolean[][] visited;
    static int[] breakdown;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        m = kb.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] = kb.nextInt();
            }
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                //ㅡ, ㅁ, ㄱ, ㄱㅡ 모양의 합 구하기
                T.solution(i, j, 0, 0);
                //ㅗ 모양의 합 구하기
                T.solution2(i, j);
            }
        }
        System.out.println(answer);

    }

    private void solution(int x, int y, int L, int sum) {
        //도형 4개 만들었으면 최댓값 넣기
        if(L == 4) {
            answer = Math.max(answer, sum);
            return;
        }

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

            //다음 지점 방문처리
            visited[nx][ny] = true;
            solution(nx, ny, L+1, sum+board[nx][ny]);
            //합 구했으면 다음 처리를 위해 미방문처리
            visited[nx][ny] = false;
        }
    }

    //+ 모양에서 한군데 빼기
    private void solution2(int x, int y) {
        //가운데를 제외한 지점의 갯수
        cnt = 4;
        //가운데를 제외한 지점의 최솟값
        min = Integer.MAX_VALUE;
        //가운데를 포함한 4개의 지점의 합
        int sum = board[x][y];
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            //cnt가 3 or 4일 때만 구해야한다. 4일 때는 최솟값을 지우기
            if(cnt <= 2) return;
            if(nx<0 || ny<0 || nx>=n || ny>=m) {
                cnt--;
                continue;
            }
            min = Math.min(min, board[nx][ny]);
            sum += board[nx][ny];
        }
        //cnt가 4이면 제일 작은 지점을 빼기
        if(cnt == 4) sum -= min;
        answer = Math.max(answer, sum);
    }
}