[삼성 SW 역량테스트] 백준 온라인 저지(BOJ) 14500번 테트로미노

14500번 주사위 굴리기

 

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

14500번: 테트로미노

 

문제 해석

---

테트리스 게임을 조금 활용한 문제같습니다. 문제는 간단합니다.

어떤 판에 숫자들이 적혀있는데 여기서 테트리스모양으로 숫자를 골라 가장 최대가 나오는 값을 구하는 문제입니다.

테트리스 모양은 여러분들이 잘 아시죠? 여기서 물론 테트리스의 블록들은 4방향 회전이 가능합니다.

 

예제를 직접 풀어보도록 하지요. 아래의 문제의 첫번째 예제가 주어졌습니다.

1	2	3	4	5
5	4	3	2	1
2	3	4	5	6
6	5	4	3	2
1	2	1	2	1

여기서 가장 큰 수를 고르면 파랑색의 숫자들이 되겠습니다. 이 외에 더 큰 값을 테트리스 모양대로 고를수가 없는 것을 알 수 있습니다.

 

 

제약 조건

---

세로와 가로의 길이(N,M)은 4이상 500이하로 주어집니다. 입력으로 주어지는 수는 1000을 넘지 않는다고 합니다.

 

풀이

---

이 문제를 이전에 JAVA로 풀어놓은게 있으므로 이번 포스팅은 JAVA 코드로 구현했습니다.

 

가로와 세로의 길이는 최대 500이며, 숫자들은 모두 500x500으로 250,000개가 되겠네요. 또 이 중 최대 4개의 숫자만 더하면 되니 문제의 답은 총 4000을 초과하지 않습니다.

이와 같이 문제의 값의 범위가 적을때는 brute-force(전수조사)로 그 문제의 해답을 찾을 수 있습니다. 모든 가능한 수를 구하는 것입니다.

문제를 풀기에 앞서 손으로 테트리스 모양을 만듭시다. 총 7개의 모양을 가지고 있고, 4방향으로 회전을 하기 때문에 대략 28개의 테트리스 모양을 배열로 만들겁니다.

1은 블록이 있는 공간을 말하고 0은 블록이 없는 공간을 의미합니다. 이해가 더 잘가기 위해 아래 세가지 테트리스 블록을 그림으로 첨부했습니다.

 

 

 

이제 이것을 배열로 만드는 것이죠. 이렇게 말이죠. 이 정도 약간의 노가다는 해도 괜찮아요. 시간이 그렇게 많지 않으니까요.

 

 

static int [][][]shapes={
		{{1,1,1,1}},{{1},{1},{1},{1}}, 
		{{0,1,0},{1,1,1}},{{1,1,1},{0,1,0}},{{0,1},{1,1},{0,1}},{{1,0},{1,1},{1,0}},
		{{1,1,1},{1,0,0}},{{0,0,1},{1,1,1}},{{1,1},{0,1},{0,1}},{{1,0},{1,0},{1,1}},
		{{1,1,1},{0,0,1}},{{1,0,0},{1,1,1}},{{0,1},{0,1},{1,1}},{{1,1},{1,0},{1,0}},
		{{1,1},{1,1}},
		{{1,0},{1,1},{0,1}},{{0,1,1},{1,1,0}},
		{{0,1},{1,1},{1,0}},{{1,1,0},{0,1,1}}
};

 

배열 첫번째 모양은 일자모양(l)이고, 두번째는 ㅗ모양입니다. 세번째 모양은 L자 모양이 되겠습니다. 이것을 사방으로 회전하다 보니까 2차원 배열이 한 줄에 최대 4개까지 나오며, 일자모양과 정사각형 모양 등 네 방향으로 회전할때 같은 모양이 나올 경우는 4개까지 나오지 않지요.

 

실제 문제를 푸는 코드는 아래에 있습니다. 

static int maxValue(int y,int x){
		int max=0;
		for(int next=0;next<19;next++){
			int r=shapes[next].length;
			int c=shapes[next][0].length;
			if(y+r>n||x+c>m) continue;
			int sum=0;
			for(int i=y;i<y+r;i++) for(int j=x;j<x+c;j++)
				sum+=map[i][j]*shapes[next][i-y][j-x];
			max=Math.max(max, sum);
		}
		return max;
	}

 

인자로 받은 y와 x는 비교할 위치를 말합니다. y는 세로축, x는 가로축의 좌표라고 보면 됩니다.

 

우리는 회전해서 나온 각각의 모양 19개(3차원 배열속의 2차원 배열 갯수)를 위에서 만들었지 않았나요? 그러니 for문을 19번 반복을 하는 겁니다.

이 for문 안에 r과 c는 만들었던 모양의 가로 길이, 세로 길이를 나타냅니다. 만약 {{ 0,1,0 }, { 1,1,1 }}의 (ㅗ)모양이라면 r의 값은 2, c의 값은 3이 되는 겁니다. 이런 길이가 입력 받은 보드의 범위를 넘어가게 되면 구할 필요가 없어지지요.

그런 조건을 if문으로 거릅니다.

int r=shapes[next].length;
int c=shapes[next][0].length;
if(y+r>n||x+c>m) continue;

 

범위 안에 있다면 이제 더해주면 됩니다. 우리가 블록이 있는 경우에는 1을 저장했었죠? 블록이 없는 경우는 0을 저장했었습니다. 그래서 판의 숫자에 이 이차원 배열을 단지 곱해주면 됩니다. 이 값을 모두 더하는 것이죠.

sum+=map[i][j]*shapes[next][i-y][j-x];

 

 

이제 모든 판의 좌표를 돌면서 가장 큰 값을 구하면 그게 답이 되는 겁니다. 전체 코드는 아래에 있습니다.

 

import java.util.Scanner;
public class Main {

	static int n,m;
	static int [][]map;
	static int [][][]shapes={
			{{1,1,1,1}},{{1},{1},{1},{1}}, 
			{{0,1,0},{1,1,1}},{{1,1,1},{0,1,0}},{{0,1},{1,1},{0,1}},{{1,0},{1,1},{1,0}},
			{{1,1,1},{1,0,0}},{{0,0,1},{1,1,1}},{{1,1},{0,1},{0,1}},{{1,0},{1,0},{1,1}},
			{{1,1,1},{0,0,1}},{{1,0,0},{1,1,1}},{{0,1},{0,1},{1,1}},{{1,1},{1,0},{1,0}},
			{{1,1},{1,1}},
			{{1,0},{1,1},{0,1}},{{0,1,1},{1,1,0}},
			{{0,1},{1,1},{1,0}},{{1,1,0},{0,1,1}}
	};
	public static void main(String[] ar){
		Scanner in=new Scanner(System.in);
		n=in.nextInt(); m=in.nextInt();
		map=new int[n][m];
		for(int i=0;i<n;i++) for(int j=0;j<m;j++)
			map[i][j]=in.nextInt();
		int max=0;
		for(int i=0;i<n;i++) for(int j=0;j<m;j++)
				max=Math.max(maxValue(i,j), max);
		System.out.println(max);
	}
	static int maxValue(int y,int x){
		int max=0;
		for(int next=0;next<19;next++){
			int r=shapes[next].length;
			int c=shapes[next][0].length;
			if(y+r>n||x+c>m) continue;
			int sum=0;
			for(int i=y;i<y+r;i++) for(int j=x;j<x+c;j++)
					sum+=map[i][j]*shapes[next][i-y][j-x];
			max=Math.max(max, sum);
		}
		return max;
	}
}

 

이상으로 테트로미노 문제를 풀어보았습니다.