[BOJ-14500]테트로미노 -Java

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

14500번: 테트로미노

package algo;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_14500_테트로미노 {
	static int map[][], N,M, result;
	static int dx[]= {0,0,-1,1}; //좌, 우, 상, 하
	static int dy[]= {-1,1,0,0};
	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());	
		
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		map=new int[N][M];
		result=Integer.MIN_VALUE;
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				map[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		solve();
		System.out.println(result);
	
	}
	private static void solve() {
		//좌(0)   우(1)  상(2)  하(3) 
		int block[][][]= {
				{ // ---- 도형 	
					{1,1,1}, {3,3,3}
				},
				{  // 정사각형 도형
					{1,3,0}
				},
				{
					{3,3,1},{0,0,3},{2,2,0},{1,1,2},{3,3,0},{0,0,2},{2,2,1},{1,1,3}
				},
				{
					{3,0,3},{3,1,3},{0,2,0},{0,3,0},{2,0,2},{2,1,2},{1,2,1},{1,3,1},
				},
				{
					{2,0,1},{2,1,3},{0,1,3},{2,3,0},
				}
		};
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				result=Math.max(result, calScore(i,j,block)+map[i][j]);
			}
		}
	}
	
	private static int calScore(int x, int y, int[][][] block) {
		int score=0;
		
		for(int i=0; i<5; i++) { //5가지 도형 
			for(int j=0; j<block[i].length; j++) { //도형의 경우의 수  
				int nx=x; 
				int ny=y;
				int tmpScore=0;
				for(int k=0; k<block[i][j].length; k++) { //도형 어떻게 생겼는지 
					
					if(i==4) { // ㅗ  모양은 조금 다르게 처리 하니까 따로 빼주기
						nx=x+dx[block[i][j][k]];
						ny=y+dy[block[i][j][k]];
					}
					else { //나머지 모양 
						nx+=dx[block[i][j][k]];
						ny+=dy[block[i][j][k]];
					}
					if(isBound(nx,ny)) tmpScore+=map[nx][ny]; //범위 ok면 점수+
					else {
						tmpScore=0;
						break; //범위 아니라면 break걸어주기
					}
				}
				score=Math.max(score, tmpScore); //최대 점수 갱신 
			}
		}
		return score;
	}
	private static boolean isBound(int x, int y) {
		if(x<0 || y<0 || x>=N || y>=M) return false;
		return true;
	}

}

소요시간 : 42분

 

 

우선 완탐문제입니다!!

N,M의 크기가 최대 500, 도형이 가지는 경우의 수 22

500*500*22 = 5,500,000밖에 되지 않기 때문에 완탐이 충분하다고 생각했습니다~

 

우선 도형을 그려주기 위해서 도형의 경우의수를 A4용지에 모두 그려봤습니다.

카페 불빛이 좀 어두워서 색깔이 이상하네요ㅋㅋㅋㅋ

무튼 저런식으로 도형은 대칭, 회전이 가능합니다.

도형의 한 점을 잡고 상,하,좌,우 로 몇번 움직이면 도형을 완성할 수 있는지 적어놨습니다.

그리고 그것을 구해놓은 배열이 block배열입니다.

 

각각의 도형에 0~4번까지 번호를 매겨줍니다. -> block[i]

각각의 도형에서 나오는 경우의 수를 매겨줍니다 -> block[i][j]

경우의 수에서 나온 도형을 어떻게 그리는지 매겨줍니다 -> block[i][j][k]

 

그런데 다른 도형은 한점을 기준으로 쭉 그려주면 되는데

이 도형은 자신을 기준으로 왼쪽한번, 오른쪽한번, 아래쪽한번 식으로 움직여야 합니다.

다른 도형들은 그냥 자신기준 오른쪽, 아래, 오른쪽 순으로 계속 이동하는 반면

저 도형은 자신에서 왼쪽, 자신에서 오른쪽, 자신에서 아래쪽 으로 진행하기 때문에

이것만 조심하시면 쉽게 푸실 수 있습니다~