백준 1035 자바 - 조각 움직이기 (BOJ 1035 JAVA)

문제 : boj1035

 

 

  처음엔 그리디로 풀어보려 했지만, 별다른 규칙을 찾지 못했다. 와중에 생각해보니 어차피 5x5 밖에 안되고, 조각은 최대 5개 이므로 최악의 경우라도 O(25^5*25*5) 정도로 풀 수 있다. 25^5는 5x5 크기의 보드에 5개의 조각을 모든 위치에 놓는 경우의 수이고, 해당 경우의 수에 대해 *25는 그 중 하나의 조각을 찾는 것이고, *5는 5개가 인접해있는지 확인하는 것이다.

 

  저대로는 당연히 불가능하지만, 여기에 백트래킹을 더해서 이미 나왔던 최소 이동 횟수 이상이라면 해당 경우의 수와 그 이후의 경우의 수를 중간에 중지하는 방식으로 진행한다면 어느정도 가능할 것 같아서 일단 해봤다.

 

  참고로 이 경우 모든 경우의 수는 조각이 n개 있었다면 다음과 같이 확인하면 된다.

1. 첫번째 조각을 5x5의 임의의 위치에 두고, 원래 첫번째 조각과의 거리를 구한다.

2. 두번째 조각을 5x5의 임의의 위치에 두고, 원래 두번째 조각과의 거리를 구한다.

3. ...

4. n번째 조각을 5x5의 임의의 위치에 두고, 원래 n번째 조각과의 거리를 구한다.

 

예를들어 n이 2라면 다음과 같다. (1과 2는 *이다.)

 

이 때 나올 수 있는 특정 경우에 대해 거리는 다음과 같이 구하면 된다. (Manhattan distance, Taxicab geometry)

  그럼 모든 경우에 대해 *이 나온 위치 아무대나 한 곳을 찾은 후, 거기서 dfs 등을 통해 n개만큼 진행할 수 있는지 판단한 후 n개만큼 진행할 수 있는 경우 중(즉, n개가 인접해 있다면) 가장 거리의 합이 작은 경우가 답이 된다.

 

  우선 이렇게 짠 코드는 다음과 같다. 이론적으로는 그다지 어렵지 않지만, 사실 구현하기엔 좀 복잡하긴 하다 ㅋㅋ

[ 맨 아래에 더 효율적인 코드가 있어요. 이건 중간과정이긴한데 이것도 통과됨. ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class Main {
    boolean[][] arr;
    ArrayList<Pos> piece;
    int n;
    int answer = Integer.MAX_VALUE;

    private boolean chk() {
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (arr[i][j]) {
                    Stack<Pos> stk = new Stack<>();
                    stk.add(new Pos(i, j));
                    boolean[][] v = new boolean[5][5];
                    v[i][j] = true;
                    int cnt = 0;
                    while (!stk.isEmpty()) {
                        Pos cur = stk.pop();
                        cnt++;
                        for (int dr = -1; dr <= 1; dr++) {
                            for (int dc = -1; dc <= 1; dc++) {
                                if (((dr^dc)&1)!=1) continue;
                                int nr = cur.r+dr;
                                int nc = cur.c+dc;
                                if (nr<0||nr>=5||nc<0||nc>=5||v[nr][nc]||!arr[nr][nc]) continue;
                                v[nr][nc] = true;
                                stk.push(new Pos(nr, nc));
                            }
                        }
                    }
                    if (cnt == n) return true;
                    return false;
                }
            }
        }
        return false;
    }

    private void bf(int idx, int sum) {
        if (answer <= sum) return;
        if (idx == n) {
            if (chk())
                answer = sum;
            return;
        }

        for (int nr = 0; nr < 5; nr++) {
            for (int nc = 0; nc < 5; nc++) {
                if (arr[nr][nc]) continue;
                int dist = Math.abs(piece.get(idx).r-nr) + Math.abs(piece.get(idx).c-nc);
                arr[nr][nc] = true;
                bf(idx+1, sum+dist);
                arr[nr][nc] = false;
            }
        }
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        piece = new ArrayList<>();
        arr = new boolean[5][5];
        for (int i = 0; i < 5; i++) {
            String row = br.readLine();
            for (int j = 0; j < 5; j++) {
                if (row.charAt(j) == '*')
                    piece.add(new Pos(i, j));
            }
        }
        n = piece.size();
        bf(0, 0);
        System.out.println(answer);
    }

    class Pos {
        int r, c;
        public Pos(int r, int c) { this.r=r; this.c=c; }
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

 

  여기서 만족하긴 좀 아쉬우니 좀 더 줄여보자. 우선 제일 거슬리는 부분이 n개가 인접해 있는지 확인하기 위해 *이 나온 위치를 찾기 위해 *25를 사용하는 부분이다. 이걸 한방에 찾을 수 있다면 O(25^5*5)로 끝낼 수 있을 것이다.

 

  그래서 생각난 부분은, 총 칸이 5*5 밖에 안되므로 총 25비트만 있으면 체크가 가능하다. 즉, int 하나로 체크가 가능하다! 물론 구현은 위의 코드보다 더 빡쌔진다. 결국 현재 보드를 나타내는 방식이 배열이냐, int 하나냐의 차이만 있으므로 로직적으론 동일하다. 이하 코드를 참고하면 되나, 설명이 없으면 이해하기 힘들 연산에 대해 몇가지 작성하겠다.

 

1. (0,0)은 0, (0,1)은 1, ... (4,4)는 24로 나타낸다. 따라서 0부터 24까지의 int값이 a라 한다면, a/5는 칼럼, a%5는 열을 뜻한다. 예를들어 17은 (3,2) 위치를 나타낸다.

2. arr|=1<<i -> 현재 보드를 나타내는 arr에서 i번 위치를 체킹한다.

3. arr^=1<<i -> 현재 보드를 나타내는 arr에서 i번 위치의 체크를 해제한다.

4. (int)(Math.log10(arr&-arr)/Math.log10(2)); -> arr&-arr은 가장 우측의 비트 1만 냅두고 나머진 전부 0으로 바꾼 값이다. 따라서 log10(2^b)/log10(2)를 통해 아무거나 켜져 있는 i번 위치를 알 수 있다. 이걸 통해 O(25^5*5)로 가능해진다.

5. 이하의 부분 -> 그냥 보통 int[] dr = {-1, 0, 1, 0}; int[] dc = {0, 1, 0, -1}; 으로 둬서 인접한 위치로 이동하던 그거다. 어차피 비트연산 쓸꺼 선넘어서 쓰고싶어서 이렇게 해봤다. 참고로 속도는 배열 2개로 처리하는거랑 비슷하다.

for (int dr = -1; dr <= 1; dr++) {
    for (int dc = -1; dc <= 1; dc++) {
        if (((dr^dc)&1)!=1) continue;

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class Main {
    int arr;
    ArrayList<Integer> piece;
    int n;
    int answer = Integer.MAX_VALUE;

    private boolean chk() {
        for (int i = 0; i < 25; i++) {
            int start = (int)(Math.log10(arr&-arr)/Math.log10(2));
            int r = start/5;
            int c = start%5;

            Stack<int[]> stk = new Stack<>();
            stk.add(new int[]{r,c});
            boolean[][] v = new boolean[5][5];
            v[r][c] = true;
            int cnt = 0;
            while (!stk.isEmpty()) {
                int[] cur = stk.pop();
                cnt++;
                for (int dr = -1; dr <= 1; dr++) {
                    for (int dc = -1; dc <= 1; dc++) {
                        if (((dr^dc)&1)!=1) continue;
                        int nr = cur[0]+dr;
                        int nc = cur[1]+dc;
                        if (nr<0||nr>=5||nc<0||nc>=5||v[nr][nc]||(arr&(1<<nr*5+nc))==0) continue;
                        v[nr][nc] = true;
                        stk.push(new int[]{nr, nc});
                    }
                }
            }
            if (cnt == n) return true;
            return false;
        }
        return false;
    }

    private void bf(int idx, int sum) {
        if (answer <= sum) return;
        if (idx == n) {
            if (chk())
                answer = sum;
            return;
        }

        for (int i = 0; i < 25; i++) {
            if ((arr&1<<i)!=0) continue;
            int dist = Math.abs(piece.get(idx)/5-i/5) + Math.abs(piece.get(idx)%5-i%5);
            arr|=1<<i;
            bf(idx+1, sum+dist);
            arr^=1<<i;
        }
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        piece = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            String row = br.readLine();
            for (int j = 0; j < 5; j++) {
                if (row.charAt(j) == '*')
                    piece.add(i*5+j);
            }
        }
        n = piece.size();
        bf(0, 0);
        System.out.println(answer);
    }


    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}