백준 1327번 소트 게임

문제

홍준이는 소트 게임을 하려고 한다. 소트 게임은 1~N으로 이루어진 N자리의 순열을 이용한다. 이 게임에선 2보다 크거나 같고 N보다 작거나 같은 수 K가 주어진다.

홍준이가 어떤 수를 뒤집는다고 하면, 그 수부터, 오른쪽으로 총 K개의 수를 뒤집는 것이다.

예를 들어 순열이 5 4 3 2 1 이었고, 여기서 K가 3일 때, 4를 뒤집으면 5 2 3 4 1이 된다. (뒤집는 다는 소리는 순서를 역순으로 바꾼다는 것)

반드시 K개의 수를 뒤집어야하기 때문에, 처음 상태에서 2나 1을 선택하는 것은 불가능하다.

홍준이는 입력으로 들어온 순열을 오름차순으로 만들려고 한다. 오름차순으로 만들면 게임이 끝난다.

홍준이가 게임을 빨리 끝내려고 할 때, 수를 최소 몇 개 선택해야 하는지 출력하는 프로그램을 작성하시오.

문제풀이

사용한 알고리즘 : Bruteforce ( BFS 사용 )
꾸준함님 (jaimemin) 코드를 참고하여 작성하였습니다.

(1) 코드 11~45

 BFS 를 사용하여 완전탐색 ( bruteforce ) 로 탐색하는 함수를 만들어 주었습니다.
 들어온 순서를 string으로 받은 후, 완성하고자 하는 순서 ( 오름차순 ) 이 무엇인지 구해둡니다.
 완성하고자 하는 순서가 나올 때 까지 BFS 로 완전탐색을 합니다.
 pair< 만든 순서, 바꾼 횟수 > 를 저장하는 queue를 하나 만들어 놓고, 처음 입력받은 순서로 탐색을 시작합니다.
 탐색은 queue가 빌 때까지 시행합니다.
 탐색 도중 완성하고자 하는 순서를 찾은 경우 해당 바꾼 횟수를 return해줍니다.
 각 탐색마다 바꿀 수 있는 모든 경우를 다 바꿔본 후, 이전에 탐색하지 않은 순서인 경우 queue에 새로이 저장해 줍니다.