[자바] 백준 1682 - 돌리기 (boj java)

문제 : boj1682

 

  내 경우 String을 기준으로 한 bfs로 풀었다. 우선 수열이 '1,2,3,4,5,6,7,8' 이라고 한다면 이걸 String으로 "12348765"로 변경한다. 즉 수열의 순서와 관계없이 그냥 내가 알아보기 편하게 배열에 나타나는 순서대로 String으로 만들었다. 어떻게 하든 상관은 없다.

 

  마찬가지로 입력이 '6 4 2 8 1 3 5 7'일 경우 String으로는 "64287531"로 표현했다. 이런식으로 입력으로 들어온 값을 String으로 변환한걸 GOAL, 시작 수열을 String으로 변환한 "12348765"를 START라고 해보자. 그럼 이제 A, B, C, D의 4가지 변환 과정을 거쳐 START에서 GOAL로 최소 몇 번 만에 변환되는지 알 수 있으면 된다. 이걸 위해 bfs를 사용할 것이다. 이 때 A와 D는 2번 수행하면 자기자신, B와 C는 4번 수행하면 자기자신으로 되돌아오므로 모든 변환 경우를 봐도 시간복잡도상 별 문제가 없을거라 판단했다.

 

  이제 String으로 변환해서 표현한 이유는 A,B,C,D 변환 과정을 간편하게 하고싶어서이다. A,B,C,D의 변환과정을 배열 인덱스의 변화로 나타내보면 다음과 같다.

  그럼 이걸 미리 배열에 나타내둬서 변환 공식처럼 사용하면 A,B,C,D 모두 동일한 로직으로 변환이 가능하다. 이게 코드의 TRANSFORM_TYPE_RULE의 역할이다.

 

  또한 위에서 말했듯 A,B,C,D 모두 2회 혹은 4회만 반복하면 자기자신으로 돌아온다. 따라서 흔히 bfs에서 사용하던 방문체크도 필수이다. 내 경우엔 문자열로 진행했으므로 HashSet<String>으로 방문체크를 했다.

 

코드 : github

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    class S {
        String str;
        int cnt;
        public S(String str, int cnt) {
            this.str = str;
            this.cnt = cnt;
        }
    }
    private static final String START = "12348765";
    private static final int[][] TRANSFORM_TYPE_RULE = {
            {4,5,6,7,0,1,2,3},
            {3,0,1,2,7,4,5,6},
            {0,2,6,3,4,1,5,7},
            {7,1,2,3,4,5,6,0}
    };
    private String transform(String str, int type) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 8; i++) sb.append(str.charAt(TRANSFORM_TYPE_RULE[type][i]));
        return sb.toString();
    }
    private void solution() throws Exception {
        byte[] buf = new byte[15];
        new DataInputStream(System.in).read(buf, 0, buf.length);
        char[] goal = new char[8];
        for (int i = 0; i < 4; i++) goal[i] = (char) buf[i*2];
        for (int i = 7; i >= 4; i--) goal[i] = (char) buf[(11-i)*2];
        HashSet<String> v = new HashSet<>();
        Queue<S> q = new ArrayDeque<>();
        final String GOAL = new String(goal);
        q.add(new S(START, 0));
        v.add(START);
        while (!q.isEmpty()) {
            String cur = q.peek().str;
            int cnt = q.poll().cnt;
            if (cur.equals(GOAL)) {
                System.out.println(cnt);
                return;
            }
            for (int i = 0; i < 4; i++) {
                String next = transform(cur, i);
                if (v.contains(next)) continue;
                v.add(next);
                q.add(new S(next, cnt+1));
            }
        }
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}