[G4] 백준 1327번 소트 게임 C++ BFS, 해시, 너비 우선 탐색

리뷰

 

처음엔 정수를 활용하여 풀려고 했으나 로직짜는게 너무 더러워 질 것 같아서 문자열을 택했다.

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

 

문제 풀이

전역 변수

• n, k : 정수형 변수이다. 수열의 길이 n, 뒤집는 개수 k
• input, s, e : 문자열 변수이다. 수열을 입력 받을 input, 최초 수열의 상태 s, 목표 수열의 상태 e
• v : 해시를 통한 방문처리를 진행할 unordered_map, <string, int> 타입으로 초기화 해주었다.
• Now : BFS를 돌릴때 사용할 구조체, 현재 수열을 나타낼 문자열 cur과 뒤집은 횟수 정수t로 이루어져 있다.

 

함수

1. Reverse

string Reverse(string num, int index)

 

현재 문자열을 입력 받고, index부터 index + k까지의 문자열을 뒤집어 주는 함수이다.

substr을 통해 num에서 index ~ index + k까지의 부분 문자열을 추출한다.

생성한 부분 문자열을 reverse를 통해 뒤집어 준다.

replace를 통해 num의 index ~ index + k부분의 문자열을 대체하여 변경해 준다.

 

2. bfs

int bfs()

 

너비 우선 탐색을 진행하며 뒤집은 횟수의 최소값을 출력해 주는 함수

만약 목표 문자열인 s가 생성되었다면 뒤집은 횟수를 리턴해 주고, 아니라면 -1을 리턴해 준다.

 

문제풀이

1. n과 k를 입력 받아주고, 수열의 정보를 문자로 받아와 input문자열에 추가해 준다.
2. s에 input문자열을 저장해 준 뒤 input문자열을 sort한 뒤에 e에 저장해 준다.
3. bfs 함수를 실행해 준다. Now타입의 큐 q를 초기화 하고 s와 0을 인자로 넣어준다.
4. 문자열 s를 방문처리 해준 뒤에 큐가 빌때까지 while문을 통해 탐색을 시작한다.
5. 현재 큐에서 pop한 문자열이 e와 동일하다면 뒤집은 횟수 t를 리턴해 주면 된다.
6. 아니라면 0 ~ n - k번을 탐색하며 Reverse함수에 현재 문자열과 i를 인덱스를 인자로 보낸 뒤 실행한다.
7. Reverse함수에서 현재 문자열의 index에서 k번째 수까지의 문자열을 슬라이싱하여 new_string으로 저장한다.
8. reverse메서드를 통해 new_string을 뒤집어 준다.
9. replace함수를 통해 입력 문자열의 index위치부터 new_string을 덮어 씌워준 뒤 리턴해 준다.
10. 만약 리턴받은 문자가 방문처리가 되어있지 않다면 방문처리 후 큐에 삽입해 준다.
11. 위 탐색을 계속 진행하다가 큐가 빌때까지 e에 도달하지 못했다면 -1을 리턴해 준다.
12. 최종적으로 bfs함수의 리턴값을 출력해주면 된다.

 

참고 사항

벡터나 정수형 보단 문자열로 푸는게 정신건강에 좋을 것 같다!

 

 

정답 코드

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

using namespace std;

int n, k;
string input = "", s = "", e = "";
unordered_map<string, int> v;

struct Now {
	string cur;
	int t;
};

string Reverse(string num, int index) {
	string new_string = num.substr(index, k);
	reverse(new_string.begin(), new_string.end());
	num.replace(num.begin() + index, num.begin() + index + k, new_string);
	return num;
}

int bfs() {
	queue<Now> q;
	q.push({ s, 0 });
	v[s] = 1;

	while (!q.empty()) {
		Now now = q.front(); q.pop();
		string num = now.cur;
		int t = now.t;
		if (num == e) return t;
		for (int i = 0; i <= n - k; i++) {
			string result = Reverse(num, i);
			if (!v[result]) {
				v[result] = 1;
				q.push({ result, t + 1 });
			}
		}
	}
	return -1;
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		char c; cin >> c;
		input += c;
	}
	s = input;
	sort(input.begin(), input.end());
	e = input;
	cout << bfs();
}