[BOJ] 14891 톱니바퀴

Link https://www.acmicpc.net/problem/14891

Note

N, S극 중 하나를 가진 톱니 8개를 가진 톱니바퀴 4개가 입력된 값에 따른 회전을 한 뒤의 상태를 특정 점수를 통해 표현한다.

문제 자체는 크게 어렵지 않다. 현재 상태를 기준으로 돌아가야 할 톱니와, 돌지 않아야할 톱니를 구분 하기만 하면 된다.
다만 탐색을 진행 하면서 톱니를 돌리지 않아야 한다.
돌아가야할 방향을 주의하면서 값을 구하면 된다.

돌아가야할 톱니를 반복문으로 구해도 상관 없지만, 재귀함수로 구현하면 코드가 간결해지긴 한다.

알고리즘

1. 초기 상태를 받는다.
2. 기준 톱니와 회전 방향을 받은 후 돌아갸아할 톱니와 방향을 저장한다.
   1. 현재 위치를 기준으로 양 옆의 값을 탐색하고 극이 다른경우 현재 톱니가 회전하는 방향의 반대 방향으로 회전한다.
   2. 재귀 호출을 통하여 진행하며 이미 탐색한 톱니에 대해서는 탐색하지 않도록 한다.
3. 구해진 회전 방향을 기준으로 회전을 진행하며, case수만큼 반복한다.
4. 최종 톱니 상태를 기준으로 점수를 구해 출력한다.

소스코드

#include <iostream>

using namespace std;

const short MAX = 8;

char gear[4][MAX+1];
short gearsLeft[4] = { 6, 6, 6, 6 };
short gearsRight[4] = { 2, 2, 2, 2 };

void turn(int pos, bool isRight, int* check) // true - 시계방향, false - 반시계 방향
{
	check[pos] = isRight ? 1 : -1;

	if (pos < 3 && gear[pos][gearsRight[pos]] != gear[pos + 1][gearsLeft[pos + 1]] && !check[pos + 1])
		turn(pos + 1, !isRight, check);
	if (pos > 0 && gear[pos][gearsLeft[pos]] != gear[pos - 1][gearsRight[pos - 1]] && !check[pos - 1])
		turn(pos - 1, !isRight, check);

}

int main()
{
	int tcc, sum = 0;
	
	for (int i = 0; i < 4; i++)
		cin >> gear[i];

	cin >> tcc;

	while (tcc--)
	{
		int chain, order;
		int checker[4] = {};

		cin >> chain >> order;

		if (order == -1)
			turn(chain - 1, false, checker);
		else
			turn(chain - 1, true, checker);

		for (int i = 0; i < 4; i++)
		{
			if (!checker[i])
				continue;

			if (checker[i] == 1) // Right
			{
				gearsRight[i] = (gearsRight[i] == 0) ? 7 : (gearsRight[i] - 1);
				gearsLeft[i] = (gearsLeft[i] == 0) ? 7 : (gearsLeft[i] - 1);
			}
			else // Left
			{
				gearsRight[i] = (gearsRight[i] + 1) % MAX;
				gearsLeft[i] = (gearsLeft[i] + 1) % MAX;
			}
		}
	}

	for (int i = 0, score = 1; i < 4; i++, score *= 2)
	{
		// cout << i + 1 << " : " << (gearsLeft[i] + 2) % MAX << '\n'; // For Debug

		if (gear[i][(gearsLeft[i] + 2) % MAX] == '1')
			sum += score;
	}

	cout << sum;

	return 0;
}

2019-03-08 02:37:19에 Tistory에서 작성되었습니다.