BOJ_12906 : 새로운 하노이 탑

문제링크

문제 풀어보기

C++ 코드

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

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int cnt[3];
	array <string, 3 > s;
	for (int i = 0; i < 3; i++) {
		cin >> cnt[i];
		// 0 일 경우 입력이 안들어오기 때문에
		// 직접 공백을 넣어준다.
		if (cnt[i] == 0) {
			s[i] = "";
		}
		// 이외에는 직접 입력
		else {
			cin >> s[i];
		}
	}

	int ans_count[3] = { 0, 0, 0 };
	// '++' 연산자 사용을 위해 '0' 초기화
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < cnt[i]; j++) {
			ans_count[s[i][j] - 'A']++;
			// 각 단어가 몇개인지 카운트
		}
	}
	
	// map< key, value >
	// array 자체를 key 로 사용하는 것이 포인트
	map< array<string, 3>, int > d;
	queue< array<string, 3> > q;
	q.push(s);
	d[s] = 0;

	while (!q.empty()) {
		auto 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;
				auto 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;
	// 정답이 들어있는 key 값을 구현
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < ans_count[i]; j++) {
			ans[i] += 'A' + i;
		}
	}
	// value 가 정답이 된다.
	cout << d[ans] << '\n';

	
	return 0;
}