[백준 1682] 돌리기 - JAVA

https://www.acmicpc.net/problem/1682

 

BFS + 문자열 처리 + 약간의 공간지각능력? = 끔찍함

 

vst + 가지치기 + DFS로 작성하다 실행속도 보고 안돼서 바꿈

 

다음은 각각 커맨드를 실행했을 때 배열의 순서이다. i번째 숫자와 charAt(i-1)이 대응됨을 기억하면 그나마 수월했다.

 

A:87654321
B:41236785
C:13645728
D:52341678

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;

class Main {

  static int ans = Integer.MAX_VALUE;
  static String ST = "12345678", ED;

  static class Search {

    String s;
    int d;

    Search(String s, int d) {
      this.s = s;
      this.d = d;
    }
  }

  public static void main(String[] args) throws IOException {

    ED = new BufferedReader(new InputStreamReader(System.in)).readLine().replace(" ", "");

    Queue<Search> q = new ArrayDeque<>();
    Set<String> vst = new HashSet<>();
    q.offer(new Search(ST, 0));
    vst.add(ST);

    while (!q.isEmpty()) {

      Search s = q.poll();

      if (ED.equals(s.s)) {
        System.out.println(s.d);
        break;
      }

      for (int i = 0; i < 4; i++) {
        String st = move(s.s, i);

        if (!vst.contains(st)) {
          vst.add(st);
          q.offer(new Search(st, s.d + 1));
        }
      }
    }
  }

  static String move(String st, int c) {
    StringBuilder sb = new StringBuilder();
    int S = st.length();
    if (c == 0) {
      return sb.append(reverse(st.substring(4))).append(reverse(st.substring(0, 4))).toString();
    } else if (c == 1) {
      return sb.append(st.charAt(3)).append(st, 0, 3).append(st, 5, S).append(st.charAt(4))
          .toString();
    } else if (c == 2) {
      return sb.append(st.charAt(0)).append(st.charAt(2)).append(st.charAt(5)).append(st, 3, 5)
          .append(st.charAt(6)).append(st.charAt(1)).append(st.charAt(7)).toString();
    } else {
      return sb.append(st.charAt(4)).append(st, 1, 4).append(st.charAt(0)).append(st, 5, S)
          .toString();
    }
  }

  static String reverse(String st) {
    StringBuilder sb = new StringBuilder();

    return sb.append(st).reverse().toString();
  }
}