[APSS][알고스팟] 게임판덮기2 (BOARDCOVER2)

[APSS][알고스팟] 게임판덮기2 (BOARDCOVER2)

문제 정보

• 문제 ID: BOARDCOVER2
• 시간 제한: 2000ms
• 메모리 제한: 65536kb

  문제

H×W 크기의 게임판과 한 가지 모양의 블록이 여러 개 있습니다. 게임판에 가능한 많은 블록을 올려놓고 싶은데, 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있으며 이 중에서 흰 칸에만 블록을 올려놓을 수 있습니다. 이때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 격자에 어긋나게 덮거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다.

위 그림은 예제 게임판과 L 자 모양의 블록으로 이 게임판을 덮는 방법을 보여줍니다. 게임판에는 15개의 흰 칸이 있고, 한 블록은 네 칸을 차지하기 때문에 그림과 같이 최대 세 개의 블록을 올려놓을 수 있지요. 게임판과 블록의 모양이 주어질 때 최대 몇 개의 블록을 올려놓을 수 있는지 판단하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 T (T≤100)가 주어집니다. 각 테스트 케이스의 첫 줄에는 게임판의 크기 H, W (1≤H, W≤10), 그리고 블록의 모양을 나타내는 격자의 크기 R, C (1≤R, C≤10)가 주어집니다. 다음 H줄에는 각각 W 글자의 문자열로 게임판의 정보가 주어집니다. 문자열의 각 글자는 게임판의 한 칸을 나타내며, #은 검은 칸, 마침표는 흰 칸을 의미합니다. 다음 R줄에는 각 C 글자의 문자열로 블록의 모양이 주어집니다. 이 문자열에서 #은 블록의 일부, 마침표는 빈 칸을 나타냅니다.
각 게임판에는 최대 50개의 흰 칸이 있으며, 각 블록은 3개 이상 10개 이하의 칸들로 구성됩니다. 변을 맞대고 있는 두 변이 서로 연결되어 있다고 할 때, 블록을 구성하는 모든 칸들은 서로 직접적 혹은 간접적으로 연결되어 있습니다.

출력

각 테스트 케이스마다 게임판에 놓을 수 있는 최대의 블록 수를 출력합니다.

예제 입력

2
4 7 2 3
##.##..
#......
#....##
#..####
###
#..
5 10 3 3
..........
..........
..........
..........
..........
.#.
###
..#

예제 출력

3
8

Solution (시간초과)

package apss;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Boardcover2 {

        public static int W,H,R,C;
        public static int block[][];
        public static int board[][];
        public static boolean dup[];
        public static List<int[]> rotations[];
        public static int best;
        public static int blockSize;

        public static void main(String[] args) throws NumberFormatException, IOException {
                // TODO Auto-generated method stubs

                System.setIn(new FileInputStream("/Users/projooni/sample_input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

                int T = Integer.parseInt(br.readLine().trim());

                for(int tc=1; tc<=T; tc++){
                        StringTokenizer st = new StringTokenizer(br.readLine());
                        H = Integer.parseInt(st.nextToken());
                        W = Integer.parseInt(st.nextToken());
                        R = Integer.parseInt(st.nextToken());
                        C = Integer.parseInt(st.nextToken());

                        board = new int\[H\][W];
                        dup = new boolean[4];
                        block = new int\[R\][C];
                        rotations = new ArrayList[4];
                        rotations[0] = new ArrayList<int[]>();
                        rotations[1] = new ArrayList<int[]>();
                        rotations[2] = new ArrayList<int[]>();
                        rotations[3] = new ArrayList<int[]>();

                        // board 정보 입력 
                        for(int i=0; i<H; i++){
                                String row = br.readLine().trim();
                                for(int j=0; j<W; j++){
                                        int ch = row.charAt(j);
                                        if('#' == ch){
                                                board\[i\][j] = 1;
                                        }else{
                                                board\[i\][j] = 0;
                                        }
                                }
                        }

                        // block 정보 입력 
                        for(int i=0; i<R; i++) {
                                String row = br.readLine().trim();
                                for(int j=0; j<C; j++) {
                                        int ch = row.charAt(j);
                                        if('#' == ch){
                                                block\[i\][j] = 1;
                                        }else{
                                                block\[i\][j] = 0;
                                        }
                                }
                        }

                        generateRotations(block);
                        search(0);

                        bw.flush();
                        bw.write(best + "\n");

                }

                bw.close();

        } 

        // 이것만으로도 머리터짐
        // arr(block)을 시계방향으로 90도 회전한다. 
        public static int\[][] rotate(int[\][] arr){
                // 90도 회전 
                int\[][] ret = new int[arr[0].length\][arr.length];
                for(int i=0; i<arr.length; i++) {
                        for(int j=0; j<arr[0].length; j++) {
                                ret\[j\][arr.length-i-1] = arr\[i\][j];
                        }
                }
                return ret;
        }

        // block의 네 가지 회전 형태를 만들고 이들을 상대 좌표의 목록으로 변환한다.
        public static void generateRotations(int[][] block) {
                for(int rot=0; rot<4; rot++) {
                        int originY = -1;
                        int originX = -1;
                        for(int i=0; i<block.length; ++i) {
                                for(int j=0; j<block[i].length; j++) {
                                        if(block\[i\][j] == 1) {
                                                if(originY == -1) {
                                                        //가장 윗줄 맨 왼쪽에 있는 칸이 '원점' 이 된다.
                                                        originY = i;
                                                        originX = j;
                                                }
                                                // 각 칸의 위치를 원점으로부터의 상대좌표로 표현한다.
                                                rotations[rot].add(new int[] {i-originY, j-originX});
                                        }

                                }
                        }

                        // block을 시계 방향으로 90도 회전한다.
                        block = rotate(block);

                }

                // 네 가지 회전 형태 중 중복이 있을 경우 이를 제거한다. (일단 생략)
                for(int i=0; i<4; i++) {
                        for(int j=0; j<4; j++) {
                                if(i == j) {
                                        continue;
                                }
                                if(!dup[i] && rotations[i].containsAll(rotations[j])) {
                                        dup[j] = true;
                                }
                        }
                }

                // 블록이 몇 칸 짜리인지 저장해둔다.
                blockSize = rotations[0].size();

        }


        // board의 (y,x)를 type번 방법으로 덮거나, 덮었언 블록을 없앤다.
        // delta = 1 이면 덮고, -1이면 덮었던 블록을 없앤다.
        // 만약 블록이 제대로 덮이지 않은 경우 (게임판 밖으로 나가거나, 겹치거나, 검은 칸을 덮을 때) false 반환한다.
        public static boolean set(int y, int x, int type, int delta) {
                boolean ok = true;
                List<int[]> rotation = rotations[type];

                for(int i=0; i<rotation.size(); i++) {
                        int[] n = rotation.get(i);
                        int ny = y+n[0];
                        int nx = x+n[1];
                        if(ny < 0 || ny >= H || nx < 0 || nx >= W) {
                                ok = false;
                        }else if((board\[ny\][nx] += delta) > 1) {
                                ok = false;
                        }
                }

                return ok;
        }

        // placed: 지금까지 놓은 블록의 수 
        public static void search(int placed) {
                // 아직 채우지 못한 칸 중 가장 윗줄 왼쪽에 있는 칸을 찾는다.
                int y = -1, x = -1;
                for(int i=0; i<H; i++) {
                        for(int j=0; j<W; j++) {
                                if(board\[i\][j] == 0) {
                                        y = i;
                                        x = j;
                                        break;
                                }
                        }
                        if(y != -1) {
                                break;
                        }
                }

                // 기저 사례 : 게임판의 모든 칸을 처리한 경우 
                if(y == -1) {
                        best = Math.max(best, placed);
                        return;
                }

                for(int type = 0; type < 4; type++) {
                        if(dup[type]) {
                                continue;
                        }
                        // 만약 board\[y\][x]를 type 형태로 덮을 수 있으면 재귀 호출한다.
                        if(set(y,x,type,1)) {
                                search(placed+1);
                        }
                        // 덮었던 블록을 치운다.
                        set(y,x,type,-1);
                }

                // 이 칸을 덮지 않고 '막아' 둔다.
                board\[y\][x] = 1;
                search(placed);
                board\[y\][x] = 0;

                return;

        }


}

풀이

감도 안와서 책 풀이를 보고 풀었다.
난이도 ‘하’ 임에도 상당히 어려웠다. (풀이를 봤음에도)
알고리즘 과정은 아래와 같다.

1. block의 4가지 회전 모양을 저장해둔다.
2. board 내부를 순회하면서 빈칸의 경우 block 4가지 방향을 돌려보면서 들어갈 수 있는지 체크한다.
3. block이 들어간다면 재귀를 타면서 카운트를 하나 늘린다. → 카운트의 최대값을 갱신한다.
4. block이 안들어간다면 카운트를 늘리지 않고 재귀를 탄다.

답을 제출하였더니 시간초과가 났다.
중복된 block 모양을 제거하지 않고 보류한 부분이 있어서 이부분을 구현하였다.
책에서는 CPP로 구현되어 있어서 나름대로 JAVA arrayList의 containsAll을 사용해서 구현해 보았는데 여전히 시간초과가 난다.
더이상 하기 싫어서, 어차피 풀이 방식은 알았기 때문에 여기서 포기하려고 한다. ㅜㅜ