[백준/Java] 1327번 소트 게임

문제 링크

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

접근 방법

처음 문제를 읽었을 때 반드시 K 개수의 숫자를 뒤집어야함에 유의하지 않고 생각해서 K = 3이고 초기 순열이 5 4 3 2 1인 경우 숫자 1, 2는 뒤집지 못한다는 점을 놓쳐서 시간을 많이 허비했습니다. 역시 문제는 꼼꼼히 읽어야합니다.

해당 문제에서 만들 수 있는 순열을 순열이 아닌 모든 숫자를 이어붙인 하나의 숫자(또는 문자열)라고 생각해보겠습니다.

예를들어 5 4 1 2 3이라는 순열이 주어졌을 때 이를 순열로 보는 것이 아닌, 54123이라는 숫자(또는 문자열)로 생각한다면1 ~ N까지의 숫자가 하나씩 존재하고 N이 8로 매우 작기 때문에 러프하게 생각해 봤을때 어떤 순열이 주어져도 주어진 순열에서 만들 수 있는 순열의 최대 종류는 12345678 ~ 87654321가지 입니다. 이는 1억이 안되는 숫자이며 문제의 제한시간을 고려하여도 충분한 시간입니다.

앞서 계산한 12345678 ~ 87654321 가지수는 가장 최악의 경우의 수일 것이고, N이 작거나 K가 작거나 큰 경우
즉, 다양한 종류의 순열을 만들 수 없다면 가지수는 훨씬 줄어들 것입니다. 따라서 bfs를 통해 현재 순열에서 뒤집을 수 있는 모든 위치에서 순열을 뒤집어 모든 순열의 경우의 수를 만든다면 언젠가 오름차순인 순열이 나올 것입니다. (나오지 않는 경우는 만들지 못하는 경우)

이때 유의할 점은 이전에 만들었던 순열에 대해서 다시 탐색한다면 시간 초과 또는 메모리 초과가 날 것이고 이를 방지하기 위해 visited를 사용해야하는데 만들어질 수 있는 가장 큰 숫자가 87654321이므로 이를 배열에 할당한다면 메모리 초과가 날 것입니다.

따라서 중복이 불가능하고 추가와 탐색이 O(1) 시간이 소요되는 HashSet을 사용하여 visited 여부를 확인하는 것이 중요합니다.   

import java.util.*;
import java.io.*;

public class Main {
    
    public static class Pair{
        String s;
        int cnt;
        Pair(String s, int cnt){
            this.s = s;
            this.cnt = cnt;
        }
    }
    
    public static int N, K;
    public static ArrayList<Integer> list = new ArrayList<>();
    public static String number, answer;
    public static Set<String> visited = new HashSet<>();
    
    public static int bfs(String number){
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(number, 0));
        visited.add(number);
        
        while(!q.isEmpty()){
            Pair p = q.poll();
            if(p.s.equals(answer)) return p.cnt;
            
            for(int i = 0; i <= (N - K); i++){
                char[] charArr = p.s.toCharArray();
                
                for(int j = 0; j < (K / 2);j++) {
                    char tmp = charArr[i + j];
                    charArr[i + j] = charArr[i + K - 1 - j];
                    charArr[i + K - 1 - j] = tmp;
                }
                
                String n = new String(charArr);
                
                if(!visited.contains(n)){
                    Pair tmpP = new Pair(n, p.cnt + 1);
                    q.add(tmpP);
                    visited.add(tmpP.s);
                }
            }
        }
        
        return -1;
    }
    
    public static void main(String args[]) throws IOException {
    
    	// 입력 부분
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        
        StringBuffer sb = new StringBuffer();
        for(int i = 0; i < N; i++) sb.append(Integer.parseInt(st.nextToken()));
        number = sb.toString();
        
        // 정답 수열을 만드는 부분 ex) 1 2 3 4 5...
        sb = new StringBuffer();
        for(int i = 1; i <= N; i++) sb.append(i);
        answer = sb.toString();

        System.out.println(bfs(number));
    }
}

접근 방법의 아이디어를 그대로 코드로 옮겼습니다. 정답 비교를 위해 65~ 67 줄에서 오름차순 순열을 생성합니다.
bfs를 사용하여 주어진 숫자(또는 문자열)부터 K 크기 유의하여 따라 뒤집을 수 있는 숫자를 뒤집은 뒤 set에 해당
숫자(또는 문자열)이 없다면 set과 queue에 각각 추가하는 일반적인 bfs입니다.
Pair class를 선언하여 숫자와 숫자를 뒤집은 횟수를 기록하였습니다.