[백준/BOJ] 백준 12906번 : 새로운 하노이 탑

www.acmicpc.net/problem/12906

12906번: 새로운 하노이 탑

현재 상태를 vector<string> start에, 목표 상태를 vector<string> dest에 저장하여 너비 우선 탐색을 통해 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>
#include <set>
#include <queue>
#include <map>
using namespace std;

int Solve(vector<string> start, vector<string> dest)
{
	set<vector<string>> discovered;
	map<vector<string>, int> depth;
	queue<vector<string>> q;

	discovered.insert(start);
	depth.insert(make_pair(start, 0));
	q.push(start);

	while (!q.empty())
	{
		vector<string> here = q.front();
		q.pop();

		//목표 상태일때
		if (here == dest)
			return depth[here];

		//i막대의 제일 위 원판을 j로 옮기는 경우
		for (int i = 0; i < 3; i++)
		{
			for (int j = 0; j < 3; j++)
			{
				if (i == j)
					continue;

				//i막대에 아무것도 없을때
				if (here[i].size() == 0)
					continue;

				vector<string> there = here;
				string from = there[i];
				string to = there[j];
				char from_top = there[i].back();
				from.pop_back();
				to += from_top;

				there[i] = from;
				there[j] = to;

				//there 막대 상황이 처음 나왔을때
				if (discovered.count(there) == 0)
				{
					discovered.insert(there);
					depth.insert(make_pair(there, depth[here] + 1));
					q.push(there);
				}

			}
		}
	}

	return -1;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	vector<string> stick(3, "");
	int A_num = 0;
	int B_num = 0;
	int C_num = 0;

	for (int i = 0; i < 3; i++)
	{
		int input;
		string won = "";

		cin >> input;

		if (input != 0)
			cin >> won;

		for (int j = 0; j < input; j++)
		{
			if (won[j] == 'A')
				A_num++;
			else if (won[j] == 'B')
				B_num++;
			else if (won[j] == 'C')
				C_num++;
		}

		stick[i] = won;
	}

	//목표 상태 저장
	vector<string> dest_stick(3, "");

	for (int i = 0; i < A_num; i++)
		dest_stick[0] += 'A';
	for (int i = 0; i < B_num; i++)
		dest_stick[1] += 'B';
	for (int i = 0; i < C_num; i++)
		dest_stick[2] += 'C';

	cout << Solve(stick, dest_stick);

	return 0;
}