[실전 문제] tetris

1. 문제

테트리스를 해본 사람이라면 작대기 모양 테트리미노가 나오길 간절히 기다렸던 적이 있을 것이다. 지금 윤성이가 그러하다. 기다리고 기다리던 작대기 모양 테트리미노가 드디어 나온 것이다.

 

테트리스 맵은 가로로 C칸, 세로로 R칸의 C×R격자형 모양이다. 예를 들어보자. 아래 그림은 가로가 6칸, 세로가 6칸인 테트리스 맵의 상태이다.

(검정색 칸은 이미 메워져있던 칸이고, 회색칸은 이번에 메울 작대기 모양 테트리미노를 의미한다.)

 

이때 가로가 1칸이고 세로가 4칸인 1×4 직사가형 작대기 모양의 테트리미노(테트리미노는 항상 1×4)를 왼쪽에서 5번째 칸에 둘 경우 총 세줄의 수평선을 메울 수 있다. 테트리스는 한번에 여러 수평선을 메울수록 큰 점수를 얻는 게임이므로, 위 경우에서는 이 방법이 가장 높은 점수를 얻을 수 있는 방법이다.

 

윤성이를 도와 작대기 모양 테트리미노를 어디에 두었을 때 가장 높은 점수를 얻을 수 있는지 알려주자. (윤성이는 작대기 모양 테트리미노가 나왔을때 게임오버를 당할지언정 가로가 더 길도록 눕혀서 두지 않는다는 나름의 테트리스 철학이 있다.)

 

그리고 테트리스는 무조건 일자로 떨어진다. (오른쪽에서 왼쪽으로 공간을 비집고 들어가는 등의 스킬은 윤성이에겐 존재하지않는다.)

---

입력

첫 줄에는 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 20이다. 그다음 줄 부터 총 R줄에 걸쳐 맵의 상태를 나타내는 숫자들이 공백을 사이에 두고 주어진다. 0은 아직 채워지지 않은 칸을 나타내며 1은 채워져있는 칸을 나타낸다.

출력

작대기를 왼쪽에서 X번째 자리에 두었을 때 가장 높은 점수를 얻을 수 있고 그 때 완전히 메워지는 수평선의 개수가 Y개라면, Y를 최대로 만드는 X와 그 때의 Y를 하나의 공백을 사이에 두고 출력해야 한다.

 

만약 어떤 자리에 두어도 수평선을 하나도 메울 수 없거나 게임오버가 일어나는 경우라면 X와 Y를 둘다 0으로 출력한다.(게임오버는 새로 내려온 작대기가 맵상을 벗어난 경우에 일어난다. 새로나온 작대기가 맵의 가장자리에 걸쳐있는 경우는 게임오버가 아니다.)

예제 입력

6 7
0 0 0 0 0 0
0 0 0 0 0 0
1 1 1 0 0 1
1 1 1 0 0 1
1 1 1 0 1 1
1 1 1 0 1 1
1 1 1 0 1 1

예제 출력

4 3

 

 

 

2. 풀이

tetris 문제는 나름 생각을 해야하는 문제이다. 가장 핵심적인 것은, 테트리미노(1x4)를 넣을 수 있는 위치를 판단하는 것이다. 테트리미노는 위에서부터 아래로 내려오기 때문에 각 열마다 위에서 부터 0의 개수를 세어, 해당 갯수가 테트리미노의 사이즈(4)보다 크다는 조건을 만족한다면 테트리미노를 넣을 수 있다고 판단하도록한다.

 

코드상에서는 isValidLocation 배열을 이용하여 테트리미노를 넣을 수 있는 열을 인덱스로, 어디서부터 쌓을 수 있는지에 대한 정보(행)를 값으로 넣어 해결한다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        StringTokenizer st = new StringTokenizer(br.readLine());
        int c = Integer.parseInt(st.nextToken()); // (5 이상)
        int r = Integer.parseInt(st.nextToken()); // (20 이하)

        int[][] arr = new int[r+1][c+1];
        for(int i = 1; i <= r; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= c; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        /* 
        테트리미노를 놓을 수 있는 위치를 판단하는 코드
        - 가장 위에서부터 막대기가 내려오기 때문에 위에서부터 0인 갯수를 카운트
        - 카운트한 갯수가 테트리미노의 사이즈(4)보다 클 경우 해당 자리에 테트리미노를 놓을 수 있다고 판단
        
        isValidLocation[4] = 7 라는 뜻은, (7, 4) 부터 막대기를 채울 수 있다는 뜻
        isValidLocation[5] = 4 라는 뜻은, (4, 5) 부터 막대기를 채울 수 있다는 뜻
         */
        int[] isValidLocation = new int[c+1];
        for(int j = 1; j <= c; j++) {
            int count = 0;
            int x = 0; // 테트리미노를 놓을 수 있는 행의 위치를 담는 변수
            for(int i = 1; i <= r; i++) {
                if(arr[i][j] == 0) {
                    count++;
                    x = i;
                }
                if(arr[i][j] == 1) break;
            }
            if(count >= 4) {
                isValidLocation[j] = x;
            }
        }

        int[] result = new int[c+1];
        for(int j = 1; j <= c; j++) {
            int x = isValidLocation[j];
            if(x > 0) {
                // 테트리미노 채우기
                for(int k = 0; k < 4; k++) {
                    arr[x-k][j] = 1;
                }

                // 매워지는 수평선 검사
                int line = 0;
                for(int k = 1; k <= r; k++) {
                    int rowCount = 0;
                    for(int p = 1; p <= c; p++) {
                        if(arr[k][p] == 1) rowCount++;
                    }
                    // 한 행이 모두 1일 경우 삭제가 가능하다고 판단
                    if(rowCount == c) line++;
                }
                // result[4] = 3 이라는 뜻은 4열에 테트리미노를 놓았을 때 삭제 되는 개수
                // result[5] = 0 이라는 뜻은 5열에 테트리미노를 놓았을 때 삭제 되는 개수
                result[j] = line;

                // 테트리미노 삭제 (원상 복구)
                for(int k = 0; k < 4; k++) {
                    arr[x-k][j] = 0;
                }
            }
        }

        int max = 0;
        int location = 0;
        for(int i = 1; i <= c; i++) {
            if(max < result[i]) {
                location = i;
                max = result[i];
            }
        }
        bw.write(location + " " + max);

        br.close();
        bw.flush();
        bw.close();
    }
}