[백준 BOJ14891] 톱니바퀴 (C++)

1. 제목

- 백준 14891 톱니바퀴

- BOJ 14891 톱니바퀴

문제 링크 : 14891번: 톱니바퀴 (acmicpc.net)

14891번: 톱니바퀴

---

2. 풀이 과정

기본적으로 문제에서 톱니의 상태를 12시 방향부터 순서대로 0 또는 1로 주고 있어요. 즉 8개의 숫자들은

위와 같은 01234567 구조를 가지고 있어요.

이거를  오른쪽으로 회전 시킨다면

70123456으로 표현이 가능해요. 마찬가지로 왼쪽으로 회전시키면

12345670이 될 거예요. 그래서 전 톱니의 상태를 문자열로 저장한 다음 회전을 처리해줄 때 

우측 회전은 gear[index] = gear[index][7] + gear[index].substr(0, 7); 

즉 8번째 상태를 맨 앞으로 보내고 나머지를 뒤에 붙였고

좌측 회전은 gear[index] = gear[index].substr(1, 7) + gear[index][0]; 

맨 앞에 값을 맨뒤에 붙이는 식으로 회전을 구현했어요. 그리고 톱니가 회전할 때 좌우를 검사해서 회전을 시켜야 하는데 코드를 보시면 이미 회전을 시킨 상태에서 비교를 하는 거라서

우측으로 회전했을 때는 인덱스가 1씩 증가를 했으니 각각 7번, 3번 인덱스를 비교해주고 좌측일 때는 이와는 반대로 1씩 감소했으니 5번, 1번 인덱스를 비교해서 회전을 시켜주고 있어요.

재귀로 돌리고 있는데 한번 돌아간 톱니는 더 이상 돌릴 필요가 없기 때문에 방문처리를 별도로 해줘서 한번 돌아간 톱니는 함수를 바로 종료하게 구현했어요.

 

---

3. 코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

string gear[6];
bool visit[6];
vector<pair<int, int>> v;
// 회전 횟수
int K;

void Reset()
{
	for (int i = 1; i < 5; i++)
	{
		visit[i] = false;
	}
}

void Rotation(int index, int dir)
{
	// 1234 톱니가 아니라면 즉시 종료
	if (index < 1 || index > 4)
		return;
	// 이미 한번 돌아간 톱니라면 즉시 종료
	if (visit[index] == true)
		return;

	// 돌아간 톱니 방문 표시
	visit[index] = true;

	// 우측방향
	if (dir == 1)
	{
		gear[index] = gear[index][7] + gear[index].substr(0, 7);

		if(gear[index][7] != gear[index - 1][2])
			Rotation(index - 1, -dir);
		if (gear[index][3] != gear[index + 1][6])
			Rotation(index + 1, -dir);
	}		
	// 좌측 방향
	else
	{
		gear[index] = gear[index].substr(1, 7) + gear[index][0];

		if (gear[index][5] != gear[index - 1][2])
			Rotation(index - 1, -dir);
		if (gear[index][1] != gear[index + 1][6])
			Rotation(index + 1, -dir);
	}
}

void Solution()
{
	int result = 0;
	// 사용하지 않는 톱니
	gear[0] = "00000000";
	gear[5] = "00000000";

	for (int i = 0; i < K; i++)
	{
		int gearIndex = v[i].first;
		int dir = v[i].second;

		Rotation(gearIndex, dir);
		Reset();
	}

	// 최종 톱니바퀴들의 12시 방향 체크
	for (int i = 1; i < 5; i++)
	{
		if (gear[i][0] == '1')
		{
			result += pow(2, i - 1);
		}
	}
	cout << result << endl;
}

void Input()
{
	for (int i = 1; i < 5; i++)
	{
		cin >> gear[i];
	}

	cin >> K;
	for (int i = 0; i < K; i++)
	{
		int gearIndex;
		int dir;
		cin >> gearIndex;
		cin >> dir;
		v.push_back({gearIndex, dir });
	}
}


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

	Input();
	Solution();

	return 0;
}