[Baekjoon,14891] 톱니바퀴

문제에서 핵심 내용은 아래의 두 가지이다.

1. 맞닿은 톱니바퀴의 극이 서로 달라야 맞물려 돌아간다.
2. 이번에 돌아가는 톱니바퀴를 확인하고 돌린다.

이를 어떻게 해야 간단히 구현할 수 있을 지 고민해보니 “재귀적으로 구현하면 어떨까?” 라는 생각이 떠올랐다. 주어진 번호의 톱니와 양측에 맞물린 3시, 9시 톱니들을 비교하여 돌릴 수 있는 경우 다음 함수를 호출하는 것이다.

구현

이를 구현한 코드를 아래에서 볼 수 있다. visited[]배열을 통해 이미 돌린 톱니바퀴는 다시 돌리지 않고 있다. 그리고 좌우측에 맞물린 톱니를 비교할 때 인덱스가 범위에 있는지 먼저 비교하고 있다. 이때 가독성을 위해 3시 방향 톱니와 9시 방향 톱니를 enum으로 선언하여 접근하고 있는 것을 눈여겨 보자.

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;

const int N = 4;

enum {THREE=2, NINE=6};

vector<string> gears;
int visited[N];

void turnGear(int idx, bool clockwise)
{
	if (visited[idx])
		return;
	visited[idx] = true;

	// 좌측 톱니바퀴와 맞물린 경우 
	if (idx - 1 >= 0 && gears[idx - 1][THREE] != gears[idx][NINE])
		turnGear(idx - 1, !clockwise);
	// 우측 톱니바퀴와 맞물린 경우
	if (idx + 1 < N && gears[idx][THREE] != gears[idx + 1][NINE])
		turnGear(idx + 1, !clockwise);

	// 톱니바퀴를 해당 방향으로 돌린다.
	if (clockwise)
		for (int i = 6;i >= 0;--i)
			swap(gears[idx][i], gears[idx][i + 1]);
	else
		for (int i = 0;i < 7;++i)
			swap(gears[idx][i], gears[idx][i + 1]);
}

int main()
{
	for (int i = 0;i < N;++i)
	{
		string s;
		cin >> s;
		gears.push_back(s);
	}

	int k;
	cin >> k;
	while (k--)
	{
		int gNum, dir;
		cin >> gNum >> dir;

		memset(visited, false, sizeof(visited));
		turnGear(gNum - 1, (dir == 1 ? true : false));
	}

	int ret = 0;
	for (int i = 0;i < N;++i)
		if (gears[i][0] == '1')
			ret += pow(2, i);

	cout << ret << endl;
	return 0;
}