[BOJ 3019] 테트리스 (Java)

BOJ 3019 테트리스

문제풀이

테트로미노 처럼 테트리스 모양을 가지고 풀이하는 문제였다. 특정 모양이 들어맞는지 확인하는 문제의 경우에는 모양을 모두 구현해놓고 대입해보는 방식이 쉬운 것 같다. 이 문제는 이미 존재하는 블럭 위의 공백에 해당하는 모든 셀에 모든 블럭을 대입하여 대입된 블럭과 기존의 블럭 사이에 공간이 존재하는지 확인하면 되는 문제였다.

• 회전하여 나올 수 있는 모든 모양을 구현해 놓고 대입해본다.
• 모든 모양은 왼쪽 아래를 기준으로 생성한다.
• 모양을 만들 때 실수하지 않도록 주의하자.

구현코드

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

public class Main {
	static final int BOTTOM = 109;
	static int[][][][] blocks =
		{
			{},	
			// 1
			{
				{{0, 0}, {-1, 0}, {-2, 0}, {-3, 0}},
				{{0, 0}, {0, 1}, {0, 2}, {0, 3}}
			},
			// 2
			{
				{{0, 0}, {-1, 0}, {-1, 1}, {0, 1}}
			},
			// 3
			{
				{{0, 0}, {0, 1}, {-1, 1}, {-1, 2}},
				{{0, 0}, {-1, 0}, {0, 1}, {1, 1}}
			},
			// 4
			{
				{{0, 0}, {0, 1}, {1, 1}, {1, 2}},
				{{0, 0}, {-1, 0}, {-1, 1}, {-2, 1}}
			},
			// 5
			{	
				{{0, 0}, {0, 1}, {-1, 1}, {0, 2}},
				{{0, 0}, {-1, 0}, {-2, 0}, {-1, 1}},
				{{0, 0}, {0, 1}, {1, 1}, {0, 2}},
				{{0, 0}, {0, 1}, {-1, 1}, {1, 1}}
			},
			// 6
			{
				{{0, 0}, {0, 1}, {0, 2}, {-1, 2}},
				{{0, 0}, {0, 1}, {-1, 0}, {-2, 0}},
				{{0, 0}, {-1, 0}, {-1, 1}, {-1, 2}},
				{{0, 0}, {0, 1}, {1, 1}, {2, 1}}
			},
			// 7
			{
				{{0, 0}, {-1, 0}, {0, 1}, {0, 2}},
				{{0, 0}, {-1, 0}, {-2, 0}, {-2, 1}},
				{{0, 0}, {0, 1}, {0, 2}, {1, 2}},
				{{0, 0}, {0, 1}, {-1, 1}, {-2, 1}}
			}
		};
	
	static int C, P;
	static int[][] map;
	static int[] height;
	static int ans;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		C = stoi(st.nextToken());
		P = stoi(st.nextToken());
		
		ans = 0;
		map = new int[110][C];
		height = new int[C];
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < C ; ++i) {
			height[i] = stoi(st.nextToken());
		}
		
		for(int i = 0 ; i < C ; ++i) {
			for(int j = BOTTOM ; j > BOTTOM - height[i] ; --j) {
				map[j][i] = 1;
			}
		}
		
		for(int i = 0 ; i < C ; ++i) {
			ans += fitting(BOTTOM - height[i], i);
		}
		
		System.out.println(ans);
	}
	
	private static int fitting(int r, int c) {
		int cnt = 0;
		
		int[][][] block = blocks[P];
		
		for(int i = 0 ; i < block.length ; ++i) {
			boolean isPossible = true;
			for(int j = 0 ; j < block[i].length ; ++j) {
				int nr = r + block[i][j][0];
				int nc = c + block[i][j][1];
				
				if(nr >= 110 || nr < 0 || nc >= C || nc < 0 || map[nr][nc] == 1) {
					isPossible = false;
					break;
				}
			}
			if(isPossible) {
				fill(r, c, block[i], 1);
				if(check(r, c, block[i])) {
					cnt++;
//					print();
//					System.out.println();
				}
				fill(r, c, block[i], 0);
			}
		}
		return cnt;
	}

	private static void fill(int r, int c, int[][] b, int item) {
		for(int i = 0 ; i < b.length ; ++i) {
			int nr = r + b[i][0];
			int nc = c + b[i][1];
			map[nr][nc] = item;
		}
	}

	private static boolean check(int r, int c, int[][] b) {
		
		for(int i = 0 ; i < b.length ; ++i) {
			int nr = r + b[i][0];
			int nc = c + b[i][1];
			if(nr < 109 && nr >= 0 && nc < C && nc >= 0 && map[nr + 1][nc] == 0) {
				return false;
			}
		}
		return true;
	}

	private static void print() {
		for(int i = 100 ; i < map.length ; ++i) {
			for(int j = 0 ; j < C ; ++j) {
				if(map[i][j] == 1) System.out.print("◼︎");
				else System.out.print("◻");
			}
			System.out.println();
		}
	}
	
	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}