게임판 덮기 (문제 ID: BOARDCOVER, 난이도: 하)

입력

전체 입력의 첫줄에는 테스트 케이스의 수 C 가 주어집니다.

 

각 테스트 케이싀의 첫 줄 : 두 개의 정수 H(height), W(weight) 가 주어집니다. (게임판 사이즈는 H * W )

각 테스트 둘째줄부터 H 줄만큼 W 칸만큼의 게임판 모양이 주어집니다.

게임판 모양은 # 은 검은 칸을 . 는 흰 칸을 나타냅니다.

 

 

출력

흰 칸을 세 칸짜리 L자 모양으로 덮어야 합니다.

한 줄에 하나씩 흰 칸을 모두 덮는 방법의 수를 출력합니다.

 

 

 

 

package com.luigi.examples.level1;


import java.awt.*;

public class BoardCover {

    public static final int WHITE_COLOR = 5;
    public static void main(String[] args) {
        String[] inputStrs = new String[]{
                "3" // 총 테스트 케이스는 3 개
                ,"3 7" // case 1
                , "#.....#"
                , "#.....#"
                , "##...##"
                , "3 7" // case 2
                , "#.....#"
                , "#.....#"
                , "##..###"
                , "8 10" // case 3
                , "##########"
                , "#........#"
                , "#........#"
                , "#........#"
                , "#........#"
                , "#........#"
                , "#........#"
                , "##########"
        };


        solution(inputStrs);
    }

    public static int solution(String[] inputStrs) {
        final int totalCase = Integer.parseInt(inputStrs[0]);

        for(int lineIndex=1, totalLine=inputStrs.length, caseNum=1; lineIndex < totalLine && caseNum <= totalCase ; caseNum++) {
            int height = Integer.parseInt(inputStrs[lineIndex].split(" ")[0]);
            int weight = Integer.parseInt(inputStrs[lineIndex].split(" ")[1]);
            String[] colorLines = new String[height];
            lineIndex++; // move to string lines
            for(int i=0; i<height; i++, lineIndex++) {
                colorLines[i] = inputStrs[lineIndex];
                System.out.println("line." + i + " : " + colorLines[i]);
            }


            ColorBoard colorBoard = new ColorBoard(height, weight, colorLines);

            System.out.println("case." + caseNum + " : " + colorBoard.countAvailable(new Point(0, 0)));
            System.out.println("");
        }

        return 0;
    }

    public static class ColorBoard {
        public int height;
        public int weight;

        int[][] board; // 0 is black, 5 is white

        public ColorBoard(int height, int weight, String[] colorLines) {
            this.height = height;
            this.weight = weight;

            board = new int[height][weight];
            System.out.println("height : " + height);
            System.out.println("weight : " + weight);
            for(int i=0; i<colorLines.length; i++) {
                char[] tokens = colorLines[i].toCharArray();
                for(int j=0; j<tokens.length; j++) {
                    if(!String.valueOf(tokens[j]).equals("#")) {
                        this.board[i][j] = WHITE_COLOR;
                    }
                }
            }

            print();
        }

        private Point moveToNext(Point cursor) {
            if(cursor.x +1 < weight) {
                return new Point(cursor.x+1, cursor.y);
            } else if(cursor.y + 1 < height) {
                return new Point(0, cursor.y + 1);
            }

            return null;
        }


        private boolean isAllUsed() {
            boolean isAllUsed = true;
            for(int i=0; i<height; i++) {
                for(int j=0; j<weight; j++) {
                    // 하나라도 흰색이 남아있으면 실패
                    if(board[i][j] == 5) {
                        isAllUsed = false;
                        break;
                    }
                }
            }

            return isAllUsed;
        }
        public int countAvailable(Point cursor) {
            if(isLastPoint(cursor)) {
                if(isAllUsed()) {
                    return 1;
                } else {
                    return 0;
                }
            }


            if(board[cursor.y][cursor.x] < 5) {
                return countAvailable(moveToNext(cursor));
            }

            int total = 0;
            if(isAvailableType1(cursor)) {
                // set 1
                setType1(cursor);
                total += countAvailable(moveToNext(cursor));
                removeType1(cursor);
                //
            }

            if(isAvailableType2(cursor)) {
                // set 2
                setType2(cursor);
                total += countAvailable(moveToNext(cursor));
                removeType2(cursor);
                //
            }

            if(isAvailableType3(cursor)) {
                // set 3
                setType3(cursor);
                total += countAvailable(moveToNext(cursor));
                removeType3(cursor);
                //
            }

            if(isAvailableType4(cursor)) {
                // set 1
                setType4(cursor);
                total += countAvailable(moveToNext(cursor));
                removeType4(cursor);
                //
            }

            return total;
        }

        private boolean isLastPoint(Point cursor) {
            if(cursor.x == weight-1 && cursor.y == height-1) {
                return true;
            } else {
                return false;
            }
        }

        private void setType1(Point cursor) {
            setColor(type1(cursor), 1);
        }

        private void setType2(Point cursor) {
            setColor(type2(cursor), 2);
        }

        private void setType3(Point cursor) {
            setColor(type3(cursor), 3);
        }

        private void setType4(Point cursor) {
            setColor(type4(cursor), 4);
        }

        private void removeType1(Point cursor) {
            setColor(type1(cursor), WHITE_COLOR);
        }
        private void removeType2(Point cursor) {
            setColor(type2(cursor), WHITE_COLOR);
        }
        private void removeType3(Point cursor) {
            setColor(type3(cursor), WHITE_COLOR);
        }
        private void removeType4(Point cursor) {
            setColor(type4(cursor), WHITE_COLOR);
        }

        private void setColor(Point[] points, int color) {
            for(Point p : points) {
                board[p.y][p.x] = color;
            }
        }

        public boolean isAvailableType1(Point cursor) {
            Point[] points = type1(cursor);
            return isAvailablePoint(points[0], points[1], points[2]);
        }
        public boolean isAvailableType2(Point cursor) {
            Point[] points = type2(cursor);
            return isAvailablePoint(points[0], points[1], points[2]);
        }
        public boolean isAvailableType3(Point cursor) {
            Point[] points = type3(cursor);
            return isAvailablePoint(points[0], points[1], points[2]);
        }
        public boolean isAvailableType4(Point cursor) {
            Point[] points = type4(cursor);
            return isAvailablePoint(points[0], points[1], points[2]);
        }
        private Point[] type1(Point cursor) {
            Point p1 = cursor;
            Point p2 = new Point(p1.x, p1.y+1);
            Point p3 = new Point(p1.x+1, p1.y+1);

            return new Point[]{p1, p2 , p3};
        }


        private Point[] type2(Point cursor) {
            Point p1 = cursor;
            Point p2 = new Point(p1.x+1, p1.y);
            Point p3 = new Point(p1.x, p1.y+1);

            return new Point[]{p1, p2 , p3};
        }
        private Point[] type3(Point cursor) {
            Point p1 = cursor;
            Point p2 = new Point(p1.x+1, p1.y);
            Point p3 = new Point(p1.x+1, p1.y+1);

            return new Point[]{p1, p2 , p3};
        }
        private Point[] type4(Point cursor) {
            Point p1 = cursor;
            Point p2 = new Point(p1.x, p1.y+1);
            Point p3 = new Point(p1.x-1, p1.y+1);

            return new Point[]{p1, p2 , p3};
        }

        private boolean isAvailablePoint(Point p1, Point p2, Point p3) {
            if(isOverflow(p1, p2, p3)) {
                return false;
            }
            try {
                int p1Color = board[p1.y][p1.x];
                int p2Color = board[p2.y][p2.x];
                int p3Color = board[p3.y][p3.x];
                if (
                        p1Color < WHITE_COLOR || p2Color < WHITE_COLOR || p3Color < WHITE_COLOR // black or already used
                ) {
                    return false;
                } else {
                    return true;
                }
            } catch (Exception e) {
                throw e;
            }
        }
        private boolean isOverflow(Point p1, Point p2, Point p3) {
            if(p1.getY() >= height || p1.getX() >= weight || p1.getX() < 0) {
                return true;
            }
            if(p2.getY() >= height || p2.getX() >= weight || p2.getX() < 0) {
                return true;
            }
            if(p3.getY() >= height || p3.getX() >= weight || p3.getX() < 0) {
                return true;
            }
            return false;
        }

        public void print() {
            for(int i=0; i<height; i++) {
                for(int j=0; j<weight; j++) {
                    System.out.print(board[i][j]);
                }
                System.out.println("");
            }
        }


    }

}

 

 

코드 보충설명

* java 에서 x,y 좌표를 저장할 마땅한 클래스가 없어서, java.awt.Point 를 사용했습니다.