[알고리즘] 알고스팟 BOARDCOVER 게임판 덮기 문제

알고스팟 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;
        }
    }


}

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