백준 1327번: 소트 게임

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

 

1~n까지 수가 랜덤으로 나열되어 있을 때, 특정 위치의 수 부터 오른쪽으로  k개까지 뒤집어 정렬시키는 최소 횟수를 구하는 문제이다.

n, k가 충분히 작으므로 BFS와 Set을 이용하여 특정 위치마다 뒤집고 정렬된 상태라면 횟수를 반환하게 풀었다.

 

수열을 int[]로 정의하였으며, 정렬된 상태를 따로 확인하지 않고 정렬된 수열과 비교하여 현재 상태가 같으면 뒤집은 횟수를 반환한다.

int[] board = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
    board[i] = Integer.parseInt(st.nextToken());
}
br.close();
int[] sorted = board.clone();
Arrays.sort(sorted);

 

 

현재 상태를 나타내는 Numbers 클래스를 구성하였으며, BFS로 탐색한다. 탐색은 특정 위치에서 뒤집었을 때 새로운 상태라면 큐에 추가한다. 이전에 존재한 상태인지 확인하기 위해 Arrays.toString()으로 문자열로 바꾸고 Set<String>에 add() 시 이미 있는 값이면 false를 반환하므로 이를 이용하여 존재 여부를 파악하였다. 큐가 비었다면 정렬 불가한 상태이므로 -1을 출력한다.

Set<String> set = new HashSet<>();
set.add(Arrays.toString(board));
Deque<Numbers> queue = new ArrayDeque<>();
queue.add(new Numbers(board.clone()));
while (!queue.isEmpty()) {
    Numbers current = queue.remove();
    if (Arrays.equals(sorted, current.numbers)) {
        System.out.print(current.count);
        return;
    }
    for (int i = 0; i + k - 1 < n; i++) {
        int[] now = current.numbers.clone();
        
        for (int j = 0; j < k / 2; j++) {
            int temp = now[i + j];
            now[i + j] = now[i + k - j - 1];
            now[i + k - j - 1] = temp;
        }
        if (set.add(Arrays.toString(now))) {
            queue.add(new Numbers(now, current.count + 1));
        }
    }
}
System.out.print("-1");

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class 소트게임1327 {
    
    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()), k = Integer.parseInt(st.nextToken());
        int[] board = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            board[i] = Integer.parseInt(st.nextToken());
        }
        br.close();
        int[] sorted = board.clone();
        Arrays.sort(sorted);
        Set<String> set = new HashSet<>();
        set.add(Arrays.toString(board));
        Deque<Numbers> queue = new ArrayDeque<>();
        queue.add(new Numbers(board.clone()));
        while (!queue.isEmpty()) {
            Numbers current = queue.remove();
            if (Arrays.equals(sorted, current.numbers)) {
                System.out.print(current.count);
                return;
            }
            for (int i = 0; i + k - 1 < n; i++) {
                int[] now = current.numbers.clone();
                
                for (int j = 0; j < k / 2; j++) {
                    int temp = now[i + j];
                    now[i + j] = now[i + k - j - 1];
                    now[i + k - j - 1] = temp;
                }
                if (set.add(Arrays.toString(now))) {
                    queue.add(new Numbers(now, current.count + 1));
                }
            }
        }
        System.out.print("-1");
    }
    
    static class Numbers {
        
        int[] numbers;
        int count = 0;
        
        public Numbers(int[] numbers) {
            this.numbers = numbers;
        }
        
        public Numbers(int[] numbers, int count) {
            this.numbers = numbers.clone();
            this.count = count;
        }
        
        @Override
        public String toString() {
            return count + " " + Arrays.toString(numbers);
        }
    }
}