[BOJ] 28707 - 배열 정렬

1. 문제 정리

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

링크를 확인해보세요.

www.acmicpc.net

• 길이가 N인 배열이 주어집니다. (배열의 원소는 1 ~ 10 사잇값으로 주어집니다.)
• 다음으로 i번째 원소와 j번째 원소를 교환했을 때 드는 비용 정보를 M개 제공해줍니다.
  • 인덱스 번호는 1 ~ N 사잇값으로 제공됩니다.
• 배열을 오름차순으로 정렬하는 데 필요한 최소 비용을 출력하면 됩니다.
  • 단, 정렬하지 못할 때 -1을 출력합니다.

2. 문제 풀이

아이디어

• 바로 풀이 떠오르지 않아서 우선 알 수 있는 정보를 정리했습니다.
• (3, 2, 1) 이라는 배열이 주어지고 [2, 3, 1] 비용 정보를 준다고 했을 때
  • 저희는 (3, 2, 1)에서 (3, 1, 2) 이동 비용 1이 발생하는 것을 알 수 있습니다.
  • 반대도 마찬가지로 비용 1이 발생하는 것을 알 수 있습니다.
  • (3, 2, 1) ← 1 → (3, 1, 2)
• 위 방식으로 예제 입력을 시각화시켰더니 그래프로 보였습니다.
• 또한 저희는 (3, 2, 1)의 시작에서 끝 모양이 (1, 2, 3)임을 알 수 있었습니다.
• 결국 시작 상태에 목표 상태까지 가는 최소 비용을 구하는 문제로 바뀝니다.

결론

• 노드에서 노드의 최단 경로 문제면 간단하게 다익스트라로 해결 할수 있습니다.
• 다른 점은 인접 상태에 대한 정보를 모르므로 매번 노드에 다음 노드로 이동할 때 비용 정보를 통하여 인접 상태를 생성해야 합니다.

3. 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


class Main {

    int arrToStatus(int[] data) {
        int res = 0;

        for (int v: data) {
            res = res * 10 + v;
        }
        return res;
    }

    void statusToArr(int data, int[] res) {
        int i = res.length - 1;

        while (data > 0) {
            res[i--] = data % 10;
            data /= 10;
        }
        while (i >= 0) {
            res[i--] = 0;
        }
    }

    void solve() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //== 입력 받기 및 초기화

        // 데이터 정보 입력 받기.
        int N = Integer.parseInt(br.readLine());

        // -1 하는 이유: 원소의 범위를 0 ~ 9으로 설정하여 자릿수를 한 자리로 만들기 위함.
        int[] data = Arrays.stream(br.readLine().split(" "))
                .mapToInt(a -> Integer.parseInt(a) - 1).toArray();

        // 조작 정보 입력 받기.
        int M = Integer.parseInt(br.readLine());
        int[][] path = new int[M][];
        for (int i = 0; i < M; i++) {
            // -1 하는 이유: 인덱스 범위로 조정하기 위함.
            path[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(a -> Integer.parseInt(a) - 1).toArray();
            path[i][2] += 1; // 비용도 1일 감소 되므로 다시 1 증가.
        }

        // key: 상태, value: 비용
        HashMap<Integer, Integer> cost = new HashMap<>();

        // int[2] { 현재 상태, 현재 비용 }
        PriorityQueue<int[]> queue = 
                    new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));

        // 상태 배열 : 매번 새로운 배열로 만들지 않고 재활용하기 위함.
        int[] tempArrPath = new int[N];

        //== 처리하기
        int startPath = arrToStatus(data); // 초기 상태.
        Arrays.sort(data); // 목표 상태.

        cost.put(startPath, 0);
        queue.add(new int[] {startPath, 0});

        // 다익스트라 시작.
        while (!queue.isEmpty()) {
            int[] nowStatus = queue.poll();

            if (nowStatus[1] > cost.getOrDefault(nowStatus[0], Integer.MAX_VALUE)) {
                continue;
            }

            for (int[] p: path) {
                // intPath to arrPath -> 이런 식으로 재사용.
                statusToArr(nowStatus[0], tempArrPath);

                // swap
                int tmp = tempArrPath[p[0]];
                tempArrPath[p[0]] = tempArrPath[p[1]];
                tempArrPath[p[1]] = tmp;

                // 인접 상태에 대한 비용 계산.
                int intPath = arrToStatus(tempArrPath);
                int value = nowStatus[1] + p[2];

                if (!cost.containsKey(intPath) || cost.get(intPath) > value) {
                    cost.put(intPath, value);
                    queue.add(new int[] {intPath, value});
                }
            }
        }

        System.out.println(cost.getOrDefault(arrToStatus(data), -1));
    }

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