백준 14500번 : 테트로미노 java

이 문제는 길이가 4가 되면 종료하는 조건을 가진 dfs를 이용하여 풀면 됩니다.

이 문제에서 나온 5개의 도형은 길이가 4인 도형을 모두 나타낸 것입니다. 이 중에서 ㅏㅓㅗㅜ로 표현 가능한 하나의 형태를 제외하고는 모두 dfs를 이용하여 각각의 테트로미노의 합을 구할 수 있습니다.

바로 코드를 보면서 설명드리도록 하겠습니다.

---

import java.util.*;
import java.io.*;

public class Main{
    static LinkedList<RowCol> ll = new LinkedList<RowCol>();
    static int[] drow = {1, -1, 0, 0};
    static int[] dcol = {0, 0, 1, -1};
    static int[][] intArr;
    static boolean[][] gone;
    static int Max = 0;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        int row = Integer.parseInt(input[0]);
        int col = Integer.parseInt(input[1]);
        intArr = new int[row][col];
        gone = new boolean[row][col];

        for(int i = 0; i<row; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            for(int j = 0; j<col; j++)
                intArr[i][j] = Integer.parseInt(st.nextToken());
        }

        for(int i = 0; i<row; i++){
            for(int j = 0; j<col; j++){
                gone[i][j] = true;
                ll.offer(new RowCol(i, j));

                dfs(i, j, intArr[i][j]);

                ll.pollLast();
                gone[i][j] = false;

                exception(i, j);
            }
        }

        System.out.print(Max);
    }

//좌표를 건네받아서 push, len(길이)가 4가 되면 Max와 비교(ㅗㅜㅏㅓ 제외)
    public static void dfs(int row, int col, int sum){
        if(ll.size() == 4){
            if(sum>Max)
                Max = sum;
            return;
        }
        for (int i = 0; i < 4; i++) {
            int dr = row + drow[i];
            int dc = col + dcol[i];

            if (dr < 0 || dr >= intArr.length || dc < 0 || dc >= intArr[0].length)
                continue;

            if (!gone[dr][dc]) {
                gone[row][col] = true;
                ll.offer(new RowCol(row, col));

                dfs(dr, dc, sum + intArr[dr][dc]);

                gone[dr][dc] = false;
                ll.pollLast();
            }
        }
    }

    public static void exception(int row, int col) {
        int wing = 4;
        int min = Integer.MAX_VALUE;
        int sum = intArr[row][col];
        for (int i = 0; i < 4; i++) {
            int dr = row + drow[i];
            int dc = col + dcol[i];

            if (wing <= 2)
                return;
            if (dr < 0 || dc < 0 || dr >= intArr.length || dc >= intArr[0].length) {
                wing--;
                continue;
            }
            min = Math.min(min, intArr[dr][dc]);
            sum = sum + intArr[dr][dc];
        }

        if (wing == 4) {
            sum = sum - min;
        }
        Max = Math.max(Max, sum);
    }
}

class RowCol{
    int row, col;
    RowCol(int row,int  col){
        this.row = row;
        this.col = col;
    }
}

이 문제를 풀기 위해서 LinkedList의 길이가 4가 되면 종료하도록 dfs를 만들었고 이때 만들어진 테트로미노의 합이 원래 있던 최댓값보다 크다면 Max의 값을 변경하도록 만들었습니다.

하지만 이렇게 하면 ㅏㅓㅗㅜ와 같은 모양을 검사하지 못한다는 단점이 있었고 이를 해결하기 위해서 exception이라는 함수를 만들어서 한번 더 검사를 해줬습니다.

exception 함수는 우선 넘어온 좌표를 기준으로 십자 모양을 만들고 그 십자의 꼭짓점들을 각각 검사하여 범위 밖으로 꼭짓점이 나가면 wing변수의 값이 줄어들게 하였습니다. 이 wing 변수의 값이 2 이하가 되면 테트로미노가 아니므로 넘기고 wing이 3이면 테트로미노이기 때문에 Max와 비교하였으며 wing의 값이 4이면 꼭짓점 중에서 가장 작은 꼭짓점의 값을 sum에서 빼서 가장 값이 큰 테트로미노를 만들었습니다.

 

 

 

wing이 왼쪽의 그림과 같이 생겼다고 가정해 보겠습니다.

 

 

 

 

 

 

 

위의 그림에서 dr과 dc가 0보다 작아서 wing이 2번 줄어들면 왼쪽의 그림과 같은 모양이므로 테트로미노가 아닙니다.

 

 

 

 

 

 

처음의 그림에서 dr이 0보다 작아서 위의 꼭짓점만
사라지는 등 하나의 꼭짓점만 사라지면 이것은 테트로미노입니다.

 

 

 

 

wing이 4여서 4개의 꼭짓점이 다 남아있다면 min에
저장된 최솟값이 들어가 있는 wing을 제거합니다.

이 도형의 경우에는 아래에 있는 3 이 가장 작으므로
이를 제거합니다.