ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [알고리즘] 알고스팟 BOARDCOVER 게임판 덮기 문제
    프로그래밍/알고리즘 2019. 3. 22. 14:26

    알고스팟 BOARDCOVER

    문제 바로가기


    최근 취업준비로 알고리즘 공부를 꾸준히 하려고 노력하고 있다.

    DFS, BFS, 백트래킹 문제들을 위주로 풀어보려고 하고 있는데 생각보다 쉽지 않은 것 같다. 한 문제를 푸는데 한시간 이상 걸리는 경우가 다반사인데 실제 코딩테스트에서는 한문제를 30~1시간이내에 풀어야 하기때문에 주의해야겠다.

    이번 문제는 알고스팟에서 문제를 보다가 _난이도 하 _ 라는 말에 덥석 문제를 풀기 시작했는데.... 나에게는 난이도 하가 하가 아니었다는 사실...ㅠㅠ

    문제를 읽어보고 처음엔 백트래킹을 이용하여 금세 풀 수 있을 것이라 생각했는데 생각보다 일일히 바꿔주는 부분을 구현하는 데 오래 걸려서 결국 남들의 풀이를 참고하여 풀었다.

    다행히 백트래킹을 사용하여 푸는 것이 맞았다 하하..

    코드는 아래와 같이 짰다. 썩 깔끔한 코드는 아닌 것같다...

    package algo.Algorithms;
    
    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.StringTokenizer;
    
    /**
     * https://algospot.com/judge/problem/read/BOARDCOVER
     * 알고스팟 BOARDCOVER  난이도 하(라는데 매우 어려움 나한텐..)
     */
    public class BoardCover {
        public static int H = 0;
        public static int W = 0;
        public static int[][] map;
        public static int[][][] arr = {
                {{0, 0}, {1, 0}, {0, 1}},
                {{0, 0}, {1, 0}, {1, -1}},
                {{0, 0}, {1, 0}, {1, 1}},
                {{0, 0}, {0, 1}, {1, 1}}
        };
        public static int count = 0;
        public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        public static void main(String[] args) throws IOException {
            int C = Integer.parseInt(br.readLine().trim());
            while (C-- > 0) {
                count = 0;
                StringTokenizer st = new StringTokenizer(br.readLine());
                H = Integer.parseInt(st.nextToken());
                W = Integer.parseInt(st.nextToken());
                solution();
            }
        }
    
        private static void solution() throws IOException {
            map = new int[H][W];
    
            for (int i = 0; i < H; i++) {
                String str = br.readLine();
                for (int j = 0; j < W; j++) {
                    map[i][j] = str.charAt(j) == '#' ? 1 : 0;
                }
            }
    
            dfs();
    
            System.out.println(count);
    
        }
    
        private static void dfs() {
            Node node = findFirstWhiteBlock();
            if (node == null) {
                count++;
                return;
            }
    
        //이 부분의 코드를 좀 깔끔하게 짤 수 있을 것은데....
            outerloop:
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 3; j++) {
                    int nextX = node.x + arr[i][j][0];
                    int nextY = node.y + arr[i][j][1];
                    if (nextX < 0 || nextY < 0 || nextX >= H || nextY >= W) continue outerloop;
                    if (map[nextX][nextY] == 1) continue outerloop;
                }
                // 세팅해주고 
                set(node, arr[i], 1);
                // 재귀함수 호출
                dfs();
                // 함수가 리턴되면 세팅해준값 다시 초기화 ( 백트래킹 )
                set(node, arr[i], 0);
            }
    
    
        }
        // 세번째 인자로 들어온 값으로 set해준다.
        private static void set(Node node, int[][] arr, int num) {
            for (int j = 0; j < 3; j++) {
                int nextX = node.x + arr[j][0];
                int nextY = node.y + arr[j][1];
                map[nextX][nextY] = num;
            }
        }
    
        // 모두 다 검은색으로 칠해졌을 시에는 null을 리턴한다.
        private static Node findFirstWhiteBlock() {
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    if (map[i][j] == 0) return new Node(i, j);
                }
            }
            return null;
        }
    
        public static class Node {
            int x, y;
    
            public Node(int x, int y) {
                this.x = x;
                this.y = y;
            }
        }
    
    
    }
    

    최근 몇몇 지원한 기업에서 코딩테스트를 봤느데 몽땅 떨어졌다...
    서버개발 연습하는 게 더 즐겁고 재밌지만, 개발자를 업으로 삼고 싶으면 일단 알고리즘 공부에 몰두해야할듯하다...

    댓글

Designed by Tistory.