[백준 1327] 소트 게임 - JAVA

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

 

불태웠다. 여러모로 소득이 많은 문제였다.

 

 

시행 착오

DFS(재귀)로 구현, Set으로 매 탐색을 방문체크 했을 때도 시간초과와 오답 발생

 

경우의 수가 8!에 방문체크도 하기 때문에, 될까 싶어서 시도했다가 IDE에서 벌써 SOF가 발생했다.

이건 그렇다쳐도, 출력이 10이여야 하는 케이스에 74가 출력됐고, 코드에는 오류가 없었다.

 

이유는 DFS의 탐색 순서 때문에, depth 10인 탐색보다 depth 74인 탐색이 먼저 실행되며 답을 찾았고, 이 탐색이 Set에 방문체크 되며 depth 10인 탐색은 실행되지 않았기 때문이다. 따라서 ans = Math.min(ans, cur); 는 없는 코드가 되버린다.

 

---

 

구현

 

1.

BFS인건 찾았으나, 더 재미있는 글을 봤다.

https://www.acmicpc.net/board/view/18589

 

next_permutation을 통해, 수열인 배열 자체를 key로 지정하는 것이었다.

 

이러면 vst[87654321]를 선언할 필요 없이, vst[8! = 40320]개로 체크가 가능했다.

[1,2,3,4,5,6,7,8] => 1

[1,2,3,4,5,6,8,7] => 2

[8,7,6,5,4,3,2,1] => 8! =  40320

 

2.

문자열의 중간에 위치하는 부분 문자열을 뒤집는 법

 

원래는 substring(0, st) + StringBuilder(substring(st, ed)).reverse() + substring(ed)로 일일이 만들었다.

String의 replace에는 pattern 매칭만 있고, idx? offset? 매칭이 없었기 때문이다.

 

근데 StringBuilder에는 존재하는 것을 발견했다. 유용하게 써먹어야 겠다.

=> StringBuilder.replace(int start, int end, String str)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {

  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 {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());

    // 처음 수열
    st = new StringTokenizer(br.readLine());
    int[] num = new int[N];
    for (int i = 0; i < N; i++) {
      num[i] = Integer.parseInt(st.nextToken());
    }

    // key : 수열, value : vst[] 에서의 인덱스
    Map<String, Integer> m = new HashMap<>();
    // 8!개의 수열을 방문 체크 배열
    boolean[] vst = new boolean[8 * 7 * 6 * 5 * 4 * 3 * 2 + 1];

    // [1,2,...,N] 부터 [N,...,2,1] 까지 m에 맵핑
    int idx = 1;
    int[] a = new int[N];
    for (int i = 0; i < N; i++) {
      a[i] = i + 1;
    }
    do {
      m.put(toStr(a, N), idx++);
    }
    while (next_permutation(a));

    // BFS
    String START = toStr(num, N);
    Queue<Search> q = new ArrayDeque<>();
    vst[m.get(START)] = true;
    q.offer(new Search(START, 0));

    int ans = -1;
    while (!q.isEmpty()) {
      Search search = q.poll();

      // 오름차순이면, BFS 이므로 최단거리임. 찾자마자 종료
      if (isASC(search.s, N)) {
        ans = search.d;
        break;
      }

      for (int i = 0; i <= N - K; i++) {
        // i번째 부터 k개를 뒤집은 문자열
        String next = reverse(i, i + K, search.s);
        int key = m.get(next);
        // 탐색한 적 없는 수열이면, q에 넣고 vst[]에 방문 체크
        if (!vst[key]) {
          vst[key] = true;
          q.offer(new Search(next, search.d + 1));
        }
      }
    }
    System.out.println(ans);
  }

  static boolean isASC(String s, int N) {

    for (int i = 1; i < N; i++) {
      if (s.charAt(i) < s.charAt(i - 1)) {
        return false;
      }
    }
    return true;
  }

  // arr -> str
  static String toStr(int[] a, int N) {

    int sum = 0;
    for (int i = 0; i < N; i++) {
      sum = sum * 10 + a[i];
    }
    return String.valueOf(sum);
  }

  // 문자열 s의 st ~ ed에 해당하는 subString을 뒤집은 새 문자열 반환
  static String reverse(int st, int ed, String s) {

    return new StringBuilder(s)
        .replace(st, ed, new StringBuilder() // replacement
            .append(s, st, ed)
            .reverse()
            .toString())
        .toString();
  }


  static boolean next_permutation(int[] a) {

    int i = a.length - 2;

    while (i >= 0 && a[i] >= a[i + 1]) {
      i--;
    }

    if (i < 0) {
      return false;
    }

    int j = a.length - 1;

    while (a[i] >= a[j]) {
      j--;
    }
    swap(a, i, j);
    flip(a, i + 1, a.length - 1);
    return true;
  }

  static void swap(int[] a, int i, int j) {
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
  }

  static void flip(int[] a, int st, int ed) {
    while (st < ed) {
      swap(a, st++, ed--);
    }
  }
}