12906번 새로운 하노이 탑

array을 이용해보자.
template < typename T, size_t N > class array;
T : 데이터 타입
N : 인자의 개수
array<int,3> arr1 = {1,2,3}; // 생성과 동시에 초기화
array<double,4> arr2; // 쓰레기값 4개가 들어가있음
array를 이용하면 보다 쉽게 문자열을 다룰 수 있다.
따라서 하노이 탑을 다루기 위해 array<string,3> s;로 선언한다.
다음, dist배열 대신, 문자열 3개를 저장할 수 있도록
map<array<string,3>, int> d;를 선언한다.

#include <iostream>
#include <map>
#include <queue>
#include <array>

using namespace std;

int main() {
	int n;
	array<string, 3> s;
	for (int i = 0; i < 3; i++) {
		cin >> n;
		if (n > 0) cin >> s[i];
		else s[i] = "";
	}
	int cnt[3] = { 0,0,0 };
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < s[i].length(); j++) {
			cnt[s[i][j] - 'A']++;
		}
	}
	map<array<string, 3>, int> d;
	queue<array<string, 3>> Q;
	Q.push(s);
	d[s] = 0; //왜 0이지 -> ch가 아니라 d니까 거리가 0이징
	while (!Q.empty()) {
		array<string, 3> now = Q.front(); Q.pop();
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (i == j) continue;
				if (now[i].length() == 0) continue;
				array<string, 3> next = now;
				next[j].push_back(next[i].back());
				next[i].pop_back();
				if (d.count(next) == 0) { //바꿔보장
					d[next] = d[now] + 1;
					Q.push(next);
				}
			}
		}
	}
	array<string, 3> ans;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < cnt[i]; j++) {
			ans[i] += (char)('A' + i);
		}
	}
	cout << d[ans] << '\n';

	return 0;
}

참고자료
https://blockdmask.tistory.com/332