*완전 탐색* tetris

완전 탐색 문제입니다.

핵심

우선 세로 길이가 4인 블록을 넣을 수 있는지를 확인해야 한다. 가능하다면, 블록을 넣고 그때의 점수를 찾고, 다시 블록을 지우는 것이 핵심이다.

 

정답 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int c = sc.nextInt(); //가로
        int r = sc.nextInt(); //세로

        //값넣기
        int[][] arr = new int[r + 1][c + 1];
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        int max = 0;
        int maxindex = 0;
        for (int i = 1; i <= c; i++) { //옆으로가면서 작대기를 넣어봄
            int check = r + 1;
            for (int j = 1; j <= r; j++) {
                if (arr[j][i] == 1) {
                    check = j;
                    break;
                }
            }

            if (check >= 5) { //위에서부터 4칸짜리 막대기를 넣을수있으면 실행
                arr[check - 1][i] = 1;
                arr[check - 2][i] = 1;
                arr[check - 3][i] = 1;
                arr[check - 4][i] = 1;

                //count세기
                int count = 0;
                for (int m = 1; m <= r; m++) {
                    boolean flag = false;
                    for (int l = 1; l <= c; l++) {
                        if (arr[m][l] == 0) flag = true;
                    }
                    if (flag == false) count++;
                }

                if (max < count) {
                    max = count;
                    maxindex = i;
                }
                arr[check - 1][i] = 0;
                arr[check - 2][i] = 0;
                arr[check - 3][i] = 0;
                arr[check - 4][i] = 0;
            }
        }

        System.out.printf("%d  %d", maxindex, max);

    }
}

 

해설

이중 배열을 선언하는데, 크기를 각각 1씩 더한 이유는 0번째 값을 안 쓰기 위함이다. -> 직관적으로 이해하기 위함.

옆으로 이동하면서, 길이가 4짜리인 블록이 들어갈 수 있는지 체크한다.

여기서는 1부터 시작했으므로 5보다 크면 통과이다.

길이가 4짜리 블록이 들어갈 수 있다면, 블록을 넣은 뒤, 점수를 체크한다.

max값을 넘으면 그 점수를 max에 넣어주고, 그때의 i값(가로의 인덱스)을 maxindex에 넣어준다.

이후 넣은 막대기를 다시 빼준다.

 

 

개선점이나 오류가 있다면, 댓글 부탁드립니다.