백준 14500 테트로미노

www.acmicpc.net/problem/14500

14500번: 테트로미노

테트로미노의 블럭들

오늘 풀었던 문제는 테트로미노입니다.

CE/IM 코딩테스트에 등장했던 문제라고 하니!

잘 풀어보는 것이 좋겠네요ㅎㅎ

 

사실 도전을 했는데 방법이 이게 맞나 저게 맞나...고민하다가

다른 사람 풀이방법을 보고 풀게 되었네요ㅠㅠ

 

다음에 다시 한번 풀어봐야겠습니다.

 

그리고 백준 문제 분류에서는 브루트포스라고 분류가 되어있는데...

DFS에 분류를 하는것이 더 맞지 않나 싶네요

 

문제에 대한 설명을 하면 이렇습니다.

각 블럭을 회전 혹은 대칭 시킨 모양을 맵 위에 올려

아래에 있는 수들을 더한 값이 최대가 되는 값을 구하는 것입니다.

 

이를 구현하는 방법은 두가지입니다!

• 각 블럭이 대칭, 회전된 경우를 하나 하나 작성하기
• DFS로 1,2,3,4 번 블럭의 대칭, 회전된 경우까지 모두 찾고 5번 블럭을 따로 찾기

사실 문제를 처음 접했을때 저에게 떠오른 방법은 첫번째 방법이었는데요...

실제 코딩테스트 자리에서 구현한다면 너무 오래 걸리는 방법일것도 같고,

코드도 너무 길어져 디버깅도 어려워질 것이 뻔했습니다.

 

결국 찾아본 방법에서 나온 것이 1,2,3,4번의 모양이 사실 깊이가 4인 DFS를 통해서

커버가 가능한 것이었는데...저에겐 도저히 떠오르지 않았을 방법이네요...

 

그래서 이를 활용하고 5번 블럭에서는

DFS를 만들어두기 위한 크기가 4인 dirX, dirY 배열에서

3개씩 고르는 경우를 통해서 해결할 수 있더라구요.

 

이 부분을 브루투포스로 해결하였습니다.

 

구현한 부분은 다음과 같습니다!

• DFS를 통해 1,2,3,4번 블럭 얹어보기
• 브루트포스(5)를 통해 블럭을 얹기

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Tetromino14500 {
	int m, n;
	int[][] map;
	Point[][] tetrominos;
	boolean[][] isNotVisited;
	int[] dirY = {-1,1,0,0};
	int[] dirX = {0,0,-1,1};
	int maxSum = Integer.MIN_VALUE;
	
	public void startTetrominos() {
		int i,j;
		
		for(i=0; i<4; i++)
			Arrays.fill(isNotVisited[i], true);
		
		for(i=0; i<m; i++) {
			for(j=0; j<n; j++) {
				isNotVisited[i][j] = false;
				setTetrominos(0, 0, i, j);
				blockFour(-1, -1 ,map[i][j], i, j);
				isNotVisited[i][j] = true;
			}
		}
		
		System.out.println(maxSum);
	}
	
	public void setTetrominos(int count, int sum ,int y, int x) {
		int i, j, nextX, nextY;
		
		
		if(count == 4) {
			/*for(i=0; i<m; i++) {
				for(j=0; j<n; j++)
					System.out.print(isNotVisited[i][j] + " ");
				System.out.println();
			}
			System.out.println();*/
			
			if(maxSum < sum)
				maxSum = sum;
			
			return;
		}
		
		for(i = 0; i<4; i++) {
			nextX = x + dirX[i];
			nextY = y + dirY[i];
			
			if(nextY >= 0 && nextY <m && nextX >= 0 && nextX <n && isNotVisited[nextY][nextX]) {
				isNotVisited[y][x] = false;
				setTetrominos(count+1, sum + map[nextY][nextX], nextY, nextX);
				isNotVisited[y][x] = true;
			}
		}
	}
	
	public void blockFour(int count, int num,int sum, int y, int x) {
		int i, j, nextX, nextY;
		
		if(count == 2) {
			if(maxSum < sum)
				maxSum = sum;
			
			return;
		}
					
		for(i = num+1; i<4; i++) {
			nextX = x + dirX[i];
			nextY = y + dirY[i];
			
			if(nextY >= 0 && nextY <m && nextX >= 0 && nextX <n) {
				blockFour(count+1, i ,sum + map[nextY][nextX], y, x);
			}
		}
	}
	
	public void setNum() throws IOException{
		int i, j;
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		map = new int[m][n];
		isNotVisited = new boolean[m][n];
		
		for(i = 0; i< m; i++) {
			st  = new StringTokenizer(bf.readLine());
			for(j=0; j<n; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
	}
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		Tetromino14500 main = new Tetromino14500();
		main.setNum();
		main.startTetrominos();
	}
}