테트로미노14500

https://www.acmicpc.net/problem/14500

처음엔 19가지 정도의 도형을 만들어서 풀어야 하나 생각했는데 코드가 너무 길어지는거 같아서 다른 풀이를 보고 이해하고 시도하였다

탐색 방향을 위 아래 왼쪽 오른쪽으로 하였다

위쪽 방면으로의 탐색 흐름을 보자 생각보다 깊고 복잡하다. 탐색 방향을 위 아래 왼쪽 오른쪽으로 하였다고 말했다. 깊이우선탐색이므로 먼저 위로 4깊이 까지 올라간다

그리고 3으로 되돌아 온뒤에 3의 왼쪽 탐색하고 다시 3으로 되돌아 와서 오른쪽 탐색하고 3으로 되돌아 온다.

이때 간과하면 안되는것이 탐색할곳이 더이상 없어서 호출했던 함수로 즉 상위 레벨로 회귀할 때마다 checked 가 해제 된다는 것이다.
그럼 해제된곳은 다시 탐색 가능하게 된다. 흐름은 6에서 2로 갔다

2에서 왼쪽인 7로 탐색하고 7의 위는 탐색해제 되었으므로 재탐색 하게 되므로 8번째로 탐색하게 된다.

6번째 탐색했던곳도 12번째에 재탐색하게됨을 볼 수 있다
최종적으로 1에서 출발해서 위쪽 방향은 밑에와 같이 탐색하게된다

깊이 단계별로 탐색을 표현하면 다음과 같다. 1->2->3->4 로 이어지는 모든 도형이 탐색되고 있다. ㅗ 도형을 제외한 모든 도형이 탐색됨을 알 수 있다

그림의 모양으로 위, 아래, 왼쪽, 오른쪽 전부 탐색된다

exception_case 는 가져왔다;;

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

public class Main {

    static int rowSize;
    static int colSize;
    static int[][] paper;
    static int[] updown = {-1, 1, 0, 0};
    static int[] leftright = {0, 0, -1, 1};

    static int[][] polyomino = new int[4][2];
    static boolean[][] checked;

    static int max = Integer.MIN_VALUE;

    static int exception_case[][][] = {
            {{0,0},{0,-1},{0,1},{-1,0}},
            {{0,0},{-1,0},{1,0},{0,1}},
            {{0,0},{0,-1},{0,1},{1,0}},
            {{0,0},{-1,0},{1,0},{0,-1}}};

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

        String[] input;
        input = br.readLine().split(" ");
        rowSize = Integer.parseInt(input[0]);
        colSize = Integer.parseInt(input[1]);

        paper = new int[rowSize][colSize];
        checked = new boolean[rowSize][colSize];

        for(int i = 0; i < rowSize; ++i)
        {
            input = br.readLine().split(" ");
            for(int j = 0; j < colSize; ++j)
            {
                paper[i][j] = Integer.parseInt(input[j]);
            }
        }

        for(int i = 0; i < rowSize; ++i)
        {
            for(int j = 0; j < colSize; ++j)
            {
                if(false == checked[i][j])
                {
                    checked[i][j] = true;
                    assembly(i, j, 0);
                    checked[i][j] = false;
                }

                getExceptionCase(i, j);
            }


        }


        System.out.println(max);
    }

    static void assembly(int row, int col, int count)
    {
        if (count == 4)
        {
            max = Math.max(max, calculate());
            return;
        }

        int newRow;
        int newCol;

        polyomino[count][0] = row;
        polyomino[count][1] = col;

        for (int i = 0; i < 4; ++i)
        {
            newRow = row + updown[i];
            newCol = col + leftright[i];

            if(newRow < 0 || newRow >= rowSize || newCol < 0 || newCol >= colSize)
                continue;

            if (checked[newRow][newCol] == false)
            {
                checked[newRow][newCol] = true;
                assembly(newRow, newCol, count + 1);
                checked[newRow][newCol] = false;
            }

        }

    }

    static int calculate()
    {
        int result = 0;
        for (int i = 0; i < 4; ++i)
        {
            result += paper[polyomino[i][0]][polyomino[i][1]];
        }

        return result;
    }

    static void getExceptionCase(int x,int y){
        for(int i=0; i<4; i++){
            boolean ret = true;
            int sum = 0;

            for(int j=0; j<4; j++){
                int newRow = x + exception_case[i][j][0];
                int newCol = y + exception_case[i][j][1];

                if(newRow<0 || newCol<0 || newRow>=rowSize || newCol>=colSize){
                    ret = false;
                    break;
                }

                sum += paper[newRow][newCol];
            }

            if(ret)
                max = Math.max(max, sum);
        }
    }
}