[백준] 1327번 - 소트 게임 (C++)

1327번: 소트 게임

문제

홍준이는 소트 게임을 하려고 한다. 소트 게임은 1부터 N까지 정수로 이루어진 N자리의 순열을 이용한다. 이 게임에선 K가 주어진다. 어떤 수를 뒤집으면, 그 수부터 오른쪽으로 K개의 수를 뒤집어야 한다. 예를 들어, 순열이 5 4 3 2 1 이었고, 여기서 K가 3일 때, 4를 뒤집으면 5 2 3 4 1이 된다. 반드시 K개의 수를 뒤집어야하기 때문에, 처음 상태에서 2나 1을 선택하는 것은 불가능하다.

입력으로 들어온 순열을 오름차순으로 만들려고 한다. 게임을 최대한 빨리 끝내고 싶을 때, 수를 최소 몇 개 선택해야 하는지 구해보자.

 

 

 

입력

첫째 줄에 순열의 크기 N과 K가 주어진다. 둘째 줄에 순열에 들어가는 수가 주어진다.

 

 

 

출력

첫째 줄에 정답을 출력한다. 만약 오름차순으로 만들 수 없으면 -1을 출력한다.

제한

• 2 ≤ K ≤ N ≤ 8

 

풀이과정

문제에서 요구하는 바를 어떻게 구현할지 막막했던 문제는 오랜만이었던 거 같다.

머리로는 이해가 되지만 어떻게 코드를 구현해야할지 막막한 문제였다.

그래서 처음에는 "문제에 접근을 할 때 규칙성이 있을까? 아니면 어떠한 조건에는 어떻게 선택을 해야하나?" 등등 생각들을 하면서 다방면으로 문제에 대해서 고민을 해봤었는데 규칙성이 뚜렷하게 보이는 규칙은 발견하지 못했었다.

그래서 고민을 하다가 문제에 걸려있는 제한 조건이 2 ≤ K ≤ N ≤ 8 형식으로 생각보다 넓지않다는 것을 확인 할 수 있었고,

그리디형식으로 돌려보자라는 생각으로 풀이를 진행하여 문제를 해결하였습니다.

 

기본 로직의 개념은 모든 방법을 다 돌아서 문제에서 원하는 오름차순으로 만드는 형식은 똑같지만

dp처럼 이전의 값에서 현재의 값이 되었다면 count를 1 증가시켜서 저장하는 방식으로 문제를 진행하여 오름차순정렬이 될때까지 무한이 반복하고 모든 경우를 다 돌았음에도 오름차순 정렬이 되지않았다면 -1을 출력시키고 종료하는 방식으로 풀이를 진행하였습니다.

 

code

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <map>

int n, k;

int		bfs(std::string s)
{
	int cnt;
	std::queue <std::pair<std::string, int> > que;
	std::map <std::string, int> map;
	std::string answer, current, temp;

	for (int i = 1; i <= n; i++) {
		answer += i + '0';
	}

	que.push(std::make_pair(s, 0));
	while (!que.empty())
	{
		current = que.front().first;
		cnt = que.front().second;
		if (current == answer) return cnt;
		for (int i = 0; i <= s.length() - k; i++) {
			temp = current.substr(i, k);
			std::reverse(temp.begin(), temp.end());
			temp = current.substr(0, i) + temp + current.substr(i + k, s.length() - i - k);
			if (map[temp] != true) {
				map[temp] = true;
				que.push(std::make_pair(temp, cnt + 1));
			}
		}
		que.pop();
	}
	return (-1);
}

int		main(void)
{
	char c;
	std::string s;

	std::cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		std::cin >> c;
		s += c;
	}
	std::cout << bfs(s) << "\n";
	

	return (0);
}

 

후기

문제를 어떻게 접근을 해야할지 막막했던 문제였던 거 같다.

문제를 다 해결하고 바라보니 로직 자체는 복잡하지는 않지만 그 과정이 힘들었던 문제였다.