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

14500, 테트로미노

주어지는 최대 size 가 500*500 이며 폴리오미노의 길이는 4, 5 종류가 주어졌다.

brute force 로 충분히 커버 가능한 사이즈임을 확인할 수 있다.

문제는 도형이 대칭, 회전이 가능하다는 점.

만약 폴리오미노를 일일이 다 회전하고 대칭을 시킨다면 문제를 해결할 수는 있겠지만,

1. 시간이 너무 많이든다
2. 오류 해결 및 반례찾기가 엄청 어려워 진다.

라는 문제점이 존재한다.

따라서 이 문제를 빠르고 효율적으로 풀기 위해서는 생각이 필요했고 폴리오미노들의 공통된 특성을 찾아보아야 했다.

나는 폴리오미노의 길이가 4라는 점에 주목하여 각 폴리오미노들을 한 사각형을 고정시킨 뒤 회전, 대칭 시켜보았다.

그 결과 ㅗ 모양의 폴리오미노를 제외하고 나머지 4개의 도형이 회전, 대칭되었을 때 나올 수 있는 모양이

한 점에서 출발하여 직선 이동만 가능할 때 만들 수 있는 길이가 4인 탐색 경로
와 같다는 사실을 알게 되엇다.

즉, 한 점을 기준으로 잡았을 때 해당 점에서 ㅗ 를 제외한 폴리오미노들을 놓을 수 있는 방법은 그 점에서 dfs 혹은 bfs로 깊이 4 탐색을 하는 것과 같다.

따라서 ㅗ를 제외한 폴리오미노로 만들수 있는 최대 점수는 해당 점에서 깊이 4인 탐색으로 만들 수 있는 최대 점수와 같다.

그 다음 문제는 ㅗ 폴리오미노의 처리였다.

나는 해당 폴리오미노는 다음과 같은 방법으로 따로 계산했다.

한 점에서 위, 아래, 왼쪽, 오른쪽 방향으로 이동가능한지 체크했다.
만약 3곳으로 이동가능한다면 회전이나 대칭을 고려하지 않아도 되므로 바로 계산해줬다.

만약 이동가능한 곳이 4곳이라면 회전과 대칭을 고려해해야한다.

그 다음, 가장 작은 값을 빼주면 최대 값을 구할 수 있다.

전체 코드

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


public class Main {
    static int answer;
	static int n;
    static int m;
    static int move[][]  = {{-1,0},{1,0},{0,1},{0,-1}};
    static int map[][];
    static boolean visit[][];
    public static void main(String[] args)throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String size[] = br.readLine().split(" ");
        n = Integer.parseInt(size[0]);
        m = Integer.parseInt(size[1]);
        map = new int[n][m];
        visit = new boolean[n][m];
        answer = 0;

        for(int i=0;i<n;i++){
            String in[] = br.readLine().split(" ");
            for(int j=0;j<m;j++){
                map[i][j] = Integer.parseInt(in[j]);
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                visit[i][j]=true;
                dfs(map[i][j],1,i,j);
                plus_check(i,j);
                visit[i][j]=false;
            }
        }

        System.out.println(answer);

    }
    static void dfs(int num,int count,int row,int col){

        if(count==4){
            answer = Math.max(num,answer);
            return;
        }
        for(int i=0;i<4;i++){
            int next_row = row+move[i][0];
            int next_col = col+move[i][1];
            if(can_move(next_row,next_col)){
                visit[next_row][next_col]=true;
                dfs(num+map[next_row][next_col],count+1,next_row,next_col);
                visit[next_row][next_col]=false;
            }
        }

    }
    static boolean can_move(int row,int col){
        if(row>=0 && row<n && col>=0 && col<m){
            return !visit[row][col];
        }
        return false;
    }
    static void plus_check(int row,int col){
        LinkedList<Point> points = new LinkedList<Point>();
        int max_plus = map[row][col];
        for(int i=0;i<4;i++){
            int next_row = row+move[i][0];
            int next_col = col+move[i][1];
            if(can_move(next_row,next_col))points.add(new Point(next_col,next_row));
        }
        if(points.size()==3){
            for(Point p : points){
                max_plus += map[p.y][p.x];
            }
        }
        else if(points.size()==4){
            int min = 987654321;
            for(Point p:points){
                max_plus += map[p.y][p.x];
                min = Math.min(map[p.y][p.x],min);
            }
            max_plus -= min;
        }
        answer = Math.max(max_plus,answer);
    }
}

class Point {
    int x;
    int y;
    public Point(int x,int y){
        this.x=x;
        this.y=y;
    }
}