[백준] 3019번 테트리스

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q1000/Q3019.java

행의 길이가 정해지지 않고, 열은 정해져 있는 블록이 쌓여있는 맵이 주어진다.
이 때, 테트리스 블록 중 하나를 정해서 떨어뜨린다. 각 블록은 번호대로 다음과 같다.

각 블록들은 90도, 180도, 270도로 회전이 가능하다.
주어진 맵에 블록 하나를 정해서 떨어뜨릴때, 빈칸 없이 떨어뜨릴 수 있는 경우의 수를 출력하여라.

처음 생각

블록을 떨어뜨려야한다. 블록이 회전 될 때마다 다양한 모양이 만들어진다. 처음에는 배열로 크기를 정해서 만들어볼 생각을 하였으나이내 포기하였다.

▶ 1 그리고 3과 4 모양의 경우는 2가지 밖에 생성이 안된다. 2번은 1가지 모양밖에 없다. 

▶ 생각해보면 주어진 면에 빈틈없이 채우는 것이므로 블록의 윗모양은 상관이 없다. 아래의 형태만 가지고 따져주면 된다.

다음 생각

블록의 위쪽은 어떻게 생겼는지 생각하지 않았다. 아랫면의 모양과 주어진 맵의 모양이 똑같이 생겼다면 빈 칸 없이 해당 블록이 들어갈 수 있는 것이다! 그림으로 표현해 보면 다음과 같다.

▶ C=4로 2 1 2 0 으로 아래처럼 맵이 주어졌다 생각을 해보자.

▶ 5번 블록을 떨어 뜨린다고 가정을 하면 5번 블록의 아랫면이 만들어지는 경우의 수는 4가지가 된다.

▶ 이 아랫면을 높낮이로 표현해 보면 다음과 같이 표현할 수 있다.

▶ (0 1) (0 0 0) (1 0) (1 0 1) 로 표현이 가능하다. 따라서 이 밑면의 높이 번호와 위의 맵의 높이 번호를 비교해서 같다면 빈 틈없이 매울 수 있는 공간이 마련된다.

▶ 맵의 주어지는 높이 값은 100까지로 다양하므로 바로 블록의 높이와 비교를 하면 안되고, 해당 맵과 블록의 해당열과 다음 열의 숫자 차이를 계산해서 같다면 패스시키고 같지 않다면 빈칸이 생기는 것이므로 실패 처리를 해주었다.

다다음 생각

높이가 0으로 표현이되므로, 정수형으로는 맨 앞에 0을 사용할 수 없으므로 문자열로 표현해준뒤 charAt()을 사용하여 정수로 전환하였다.

방안

1) 모든 경우를 살펴봐야하는 완전 탐색 문제였지만 테트리스 블록 모양을 어떻게 보냐에따라서 엄청 복잡해질 수도 간단해질 수도 있는 문제였다.

▶ 만약 배열로 돌려서 만드는 구현을 했으면 엄청 복잡해졌을 것이다.

package baekjoon.q1000;
 
import java.util.Scanner;
 
public class Q3019 {
    static int c,p;
    static int[] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        c = sc.nextInt(); // 열 수
        p = sc.nextInt(); // 블록 번호
        arr = new int[c];
        for(int i=0;i<c;i++)
            arr[i] = sc.nextInt();
        
        // 결과 초기화
        result = 0;
        makeBlock();
        System.out.println(result);
    }
    
    private static void makeBlock() {
        // 블록의 아랫면만 따져주면 된다.
        switch (p) {
        case 1: // ㅣ
            solve("0");
            solve("0000");
            break;
        case 2: // ㅁ
            solve("00");
            break;
        case 3: // 지렁이
            solve("001");
            solve("10");
            break;
        case 4: // 지렁이 좌우 전환
            solve("100");
            solve("01");
            break;
        case 5: // ㅗ
            solve("000");
            solve("01");
            solve("101");
            solve("10");
            break;
        case 6: // ㄴ 좌우 전환
            solve("000");
            solve("00");
            solve("011");
            solve("20");
            break;
        case 7: // ㄴ
            solve("000");
            solve("02");
            solve("110");
            solve("00");
            break;
        }
    }
    
    static int result;
    private static void solve(String block) {
        int len = block.length();
        // 전체 열에대해서 살피기
        for(int i=0;i<=c-len;i++) {
            //해당 열에서 블록이 가지고 있는 열의 길이만큼 살피기
            boolean flag = true;
            for(int j=i;j<i+len-1;j++) {
                int now = block.charAt(j-i)-'0'; // 현재 
                int next = block.charAt(j-i+1)-'0'; // 다음
                // 블록의 아래 모양과 똑같지 않으면 통과
                if(now-next != arr[j]-arr[j+1]) {
                    flag = false;
                    break;
                }
            }
            if(flag) result++;
        }
    }
}