톱니바퀴 (feat. 백준, 14891번)

톱니바퀴
https://www.acmicpc.net/problem/14891

14891번: 톱니바퀴

반응형

// woohyeon.kim
#include <iostream>
#include <deque>
#include <queue>
#include <string>
#include <cmath>

using namespace std;

struct Gear
{
	deque<int> value;
};
Gear m_gear[4];
int K;
struct MoveInfo
{
	int gear_number;				// 1 ~ 4
	int turn_direction;				// -1 : 반시계, 1 : 시계
};
MoveInfo m_move_info[101];

// 반시계 방향으로 돌 경우
inline void turn_left(Gear& gear)
{
	auto& v = gear.value.front(); gear.value.pop_front();
	gear.value.push_back(v);
}

// 시계 방향으로 돌 경우
inline void turn_right(Gear& gear)
{
	auto& v = gear.value.back(); gear.value.pop_back();
	gear.value.push_front(v);
}

inline const int& get_gear_left(const Gear& gear)
{
	return gear.value.at(6);
}

inline const int& get_gear_right(const Gear& gear)
{
	return gear.value.at(2);
}

inline const int& get_gear_top(const Gear& gear)
{
	return gear.value.front();
}

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

	string value;
	for (auto ix = 0; ix < 4; ++ix)
	{
		cin >> value;
		for (auto iy = 0; iy < 8; ++iy)
			m_gear[ix].value.push_back(static_cast<int>(value[iy] - '0'));
	}
	cin >> K;
	for (auto idx = 0; idx < K; ++idx)
		cin >> m_move_info[idx].gear_number >> m_move_info[idx].turn_direction;

	queue<MoveInfo> doing;
	for (auto idx = 0; idx < K; ++idx)
	{
		auto& move_info = m_move_info[idx];
		doing.push(move_info);
		// 
		auto tmp_move_info = move_info;
		while (true)
		{
			// 기어 좌측에도 기어가 있는지
			if (tmp_move_info.gear_number == 1)
				break;
			auto& current_gear = m_gear[tmp_move_info.gear_number - 1];
			auto& left_gear = m_gear[tmp_move_info.gear_number - 2];
			if (get_gear_right(left_gear) == get_gear_left(current_gear))
				break;
			tmp_move_info.gear_number = tmp_move_info.gear_number - 1, tmp_move_info.turn_direction = -tmp_move_info.turn_direction;
			doing.push(tmp_move_info);
		}
		tmp_move_info = move_info;
		while (true)
		{
			// 기어 우측에도 기어가 있는지
			if (tmp_move_info.gear_number == 4)
				break;
			auto& current_gear = m_gear[tmp_move_info.gear_number - 1];
			auto& right_gear = m_gear[tmp_move_info.gear_number];
			if (get_gear_right(current_gear) == get_gear_left(right_gear))
				break;
			tmp_move_info.gear_number = tmp_move_info.gear_number + 1, tmp_move_info.turn_direction = -tmp_move_info.turn_direction;
			doing.push(tmp_move_info);
		}

		while(!doing.empty())
		{
			auto& q = doing.front(); doing.pop();
			if (q.turn_direction == -1)
				turn_left(m_gear[q.gear_number - 1]);
			else
				turn_right(m_gear[q.gear_number - 1]);
		}
	}

	auto result = 0;
	for (auto idx = 0; idx < 4; ++idx)
	{
		if (get_gear_top(m_gear[idx]) == 1)
			result += static_cast<int>(pow(2, idx));
	}
	cout << result << endl;

	return 0;
}
// *&)*@*

1. 톱니를 굴리기 이전에 좌측과 우측들의 톱니들에 대해서 검사합니다. (반드시 굴리기 이전입니다.)
2. 굴려야할 톱니가 있다면 검사 이후에 모두 돌립니다.
3. 다음 회전을 가져오고 1번을 반복합니다.