백준 15662번 톱니바퀴 (2) C++

출처 : https://www.acmicpc.net/problem/15662

회전시킬 톱니바퀴와 회전 방향을 입력받고 해당 톱니바퀴는 회전시킨 뒤, 회전시키기 전의 톱니바퀴와 맞닿아 있는 톱니바퀴가 같다면 맞닿아 있는 톱니바퀴는 회전시키지 않고, 다르다면 반대방향으로 회전시킨다. 이것을 반복하다가 회전이 끝났을 때 12시 방향에 있는 S극의 톱니바퀴의 개수를 구하는 문제이다.

 

문제를 푸는데 어려움은 딱히 없었던 것 같은데 시간은 조금 걸린 것 같다.

엄청 쉬운 문제는 아닌 것 같은데 단순히 구현만 하면 돼서 그런지 정답률이 73퍼센트나 된다는게 놀랍다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int t, k;
vector<vector<char>> wheel(1001, vector<char>(8));

void Rotate(int num, int rot) {
	if (rot == -1) {
		char tmp = wheel[num][0];
		wheel[num].erase(wheel[num].begin());
		wheel[num].push_back(tmp);
	}
	else {
		char tmp = wheel[num][7];
		wheel[num].pop_back();
		wheel[num].insert(wheel[num].begin(), tmp);
	}
}

void Solve(int num, int rot, int dir) {
	if (num == 1 && dir == -1) {
		Rotate(num, rot);
		return;
	}
	if (num == t && dir == 1) {
		Rotate(num, rot);
		return;
	}
	if (dir == 1) {
		char comp = wheel[num][2];
		char other = wheel[num + 1][6];
		Rotate(num, rot);
		if (comp != other) {
			Solve(num + 1, -rot, dir);
		}
	}
	else {
		char comp = wheel[num][6];
		char other = wheel[num - 1][2];
		Rotate(num, rot);
		if (comp != other) {
			Solve(num - 1, -rot, dir);
		}
	}
}

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

	string str;
	cin >> t;
	for (int i = 1; i <= t; i++) {
		cin >> str;
		for (int j = 0; j < 8; j++) {
			wheel[i][j] = str[j];
		}
	}
	cin >> k;
	int num, rot;
	for (int i = 0; i < k; i++) {
		cin >> num >> rot;
		Solve(num, rot, -1);
		Rotate(num, -rot);
		Solve(num, rot, 1);
	}
	int cnt = 0;
	for (int i = 1; i <= t; i++) {
	    if (wheel[i][0] == '1') cnt++;
	}
	cout << cnt;
};