[BOJ-14500] 테트로미노

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

14500번: 테트로미노

---

[풀이]

조금 비효율적인 방법으로 풀었다 ㅠㅠ

 

나는 BFS를 사용했고, 5가지의 테트로미노의 대칭/회전을 직접 만들어서 했다.

아이디어는 BFS를 이용해서 현위치에 상/하/좌/우 인접한 곳으로 이동할때

dy=(-1,1,0,0) , dx=(0,0,-1,1) 로 나타내서

다음위치가 배열안에 있는지 확인해서 큐에 넣거나 방문 등의 연산을 한것에서 떠올랐다.

 

 

모든 점에서 가능한 테트로미노를 구하여, 4개블록의 합이 최대인것을 구해야한다.

블록의 시작점을 (y,x)라 할때 테트로미노를 구성하는 블록의 위치가

N행 M열 행렬안에 있는지 확인해야한다.

 

테트로미노 블록의 종류는 5가지이다.

그런데 각 블록을 회전/대칭 하는 경우를 고려해야한다.

그래서 각 블록의 회전/대칭 까지 고려해서 3차원배열로 나타냈다. (shapey, shapex)

 

코드의 isOkay=True 는 테트로미노 블록 4개를 모두 탐색한 경우를 의미한다.

만일 어느 한부분이라도 행렬안에 있지 않는다면, 테트로미노를 형성할 수 없다.

 

 

 

 

---

[코드] JAVA

import java.util.*;

public class Main
{
	public static int N,M;
	public static int map[][]=new int[500][500];
	public static Queue q= new LinkedList<Element>();
	public static int maximum=0;
	
	//1: ㅁ
	//2: L
	//3: ㅡ
	//4: 번개
	//5: ㅗ
	public static int shapey[][][]= {
			{{0,1,1}},
			{{1,2,2}, {1,2,2},  {0,0,1},  {0,0,1}, {1,1,1}, {1,1,1}, {0,1,2}, {0,1,2} },
			{{0,0,0}, {1,2,3}},
			{{1,1,2}, {1,1,2},   {0,1,1},  {0,1,1}}, 
			{{0,0,1}, {1,1,1},  {1,1,2}, {1,1,2}}
	};
	
	public static int shapex[][][]= {
			{{1,0,1}},
			{{0,0,1}, {0,0,-1}, {1,2,2}, {1,2,0}, {0,1,2}, {0,-1,-2}, {1,1,1}, {1,0,0}},
			{{1,2,3}, {0,0,0}},
			{{0,1,1}, {0,-1,-1}, {1,0,-1}, {1,1,2}},	
			{{1,2,1}, {-1,0,1}, {0,1,0}, {-1,0,0}}
	};
	
	public static boolean isRange(int y, int x) {
		if((y>=0&& y<N)&&(x>=0 && x<M))	return true;
		return false;
	}
	
	
	public static class Element{
		int y,x;
		Element(int y, int x){
			this.y=y;
			this.x=x;
		}
	}
	
	public static int bfs(int y, int x) {
		int max_now=0;
		Element e= new Element(y,x);
		q.add(e);
		
		//큐가 비어있지 않으면
		while(!q.isEmpty()) 
		{
			
			Element now= (Element)q.poll();
			for(int i=0; i<5; i++) //테트로미노 블록 종류
			{
				
				for(int j=0; j<shapey[i].length; j++)  //블록i의 대칭/회전 모양까지 고려.
				{
					int tmp=map[now.y][now.x];
					boolean isOkay=true;
					
					for(int k=0; k<shapey[i][j].length; k++) //나머지 블록3개
					{
						int nexty=now.y+shapey[i][j][k];
						int nextx=now.x+shapex[i][j][k];
                        
						if(isRange(nexty, nextx))
						{
							tmp+=map[nexty][nextx];
						}
						else{
							isOkay=false; //이 테트로미노에서는 적용안됨.
						}
						
					}
					
					//isOkay가 true인것만 max_now와 tmp를 비교할 수 있다.
					if(isOkay) 
					{
						max_now=Math.max(max_now, tmp);
					}
					
				}
			}
			
		}
		return max_now;
	}
	
	public static void main(String[] args) {
		//입력//
		Scanner sc= new Scanner(System.in);
		N=sc.nextInt();
		M=sc.nextInt();
		for(int y=0; y<N; y++) {
			for(int x=0; x<M; x++) {
				map[y][x]=sc.nextInt();
			}
		}
		
		//테트로미노의 최댓값을 찾는다.
		for(int y=0;y<N;y++) 
			for(int x=0; x<M; x++) 
				maximum=Math.max(maximum, bfs(y,x));
		
		System.out.println(maximum);
	}
}