14891 톱니바퀴

www.acmicpc.net/problem/14891

14891번: 톱니바퀴

간단한 구현 문제지만 톱니바퀴의 회전과 이어서 회전되는 다른 톱니바퀴를 구현하는데 복잡하게 생각하여 시간을 꽤 낭비한 문제이다.

처음 통과했을 때의 코드는 회전을 구현할 때 다소 가독성이 떨어졌는데, 다른 코드를 참고해보니 덱(deque)으로 회전을 쉽게 구현할 수 있다.

1. 반시계 방향으로 회전할 때, 맨 앞의 원소를 맨 뒤에 넣음

2. 시계 방향으로 회전할 때, 맨 뒤의 원소를 맨 앞에 넣음

심플하지만 생각하지 못했던 방법이다.

또한 이어서 회전하는건 재귀함수를 통해 맞닿은 톱니가 같다면, 다음 바퀴도 회전하도록 구현했다.

정답코드

#include <iostream>
#include <string>
#include <deque>
#include <cmath>
#include <string.h>
using namespace std;
deque<int> wheel[4];
bool visit[4] = { false, };
void rotate(int start, int dir)
{
	if (visit[start] == false)
		visit[start] = true;
	else
		return;
	if (start + 1 < 4) {
		if (wheel[start][2] != wheel[start + 1][6]) {
			rotate(start + 1, -dir);
		}
	}
	if (start - 1 >= 0) {
		if (wheel[start][6] != wheel[start - 1][2]) {
			rotate(start - 1, -dir);
		}
	}
	int temp;
	if (dir == -1) {
		temp = wheel[start].front();
		wheel[start].pop_front();
		wheel[start].push_back(temp);
	}
	else {
		temp = wheel[start].back();
		wheel[start].pop_back();
		wheel[start].push_front(temp);
	}
}
int summation()
{
	int sum = 0;
	for (int i = 0; i < 4; i++) {
		if (wheel[i][0] == 1)
			sum += pow(2, i);
	}
	return sum;
}
int main()
{
	for (int i = 0; i < 4; i++) {
		string temp;
		cin >> temp;
		for (int j = 0; j < temp.length(); j++)
			wheel[i].push_back(temp[j] - '0');
	}
	int tc, start, dir;
	scanf("%d", &tc);
	for (int i = 0; i < tc; i++) {
		scanf("%d %d", &start, &dir);
		rotate(start - 1, dir);
		memset(visit, false, sizeof(visit));
	}
	int answer = summation();
	printf("%d\n", answer);
	return 0;
}