BOJ 14891 톱니바퀴 / C++

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

14891번: 톱니바퀴

백준 온라인저지 14891번 톱니바퀴 문제입니다.

 

아이디어

문제를 읽었을때 특정한 알고리즘이 생각나지 않아서 시뮬레이션 문제라고 판단하고 풀이했습니다.

톱니바퀴 개수가 4개로 정해져 있기 때문에 어느정도의 하드코딩이 허용된다고 보여집니다.

회전 명령을 받았을때 해당 톱니바퀴에 의해 영향을 받는 톱니바퀴들을 모아서 한번에 회전시키는 방식으로 처리했고, 원하는 순서로 진행하는 코드를 만들기 위해 메서드들을 행위에 맞게 설계하려고 노력했습니다. vector를 자료구조로 사용했습니다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> Gear(4, vector<int>(8, 0));
vector<pair<int, int>> order;

//점수 계산하는 함수
int findScore() {
	int score = 0;
	for (int i = 0; i < Gear.size(); i++) {
		if (Gear[i][0]) {
			score += 1 << i;
		}
	}
	return score;
}

//영향받는 바퀴가 회전해야하는지 판단하는 함수 / p : 회전 바퀴, c : 영향받는 바퀴
bool chekTrun(int p, int c) {
	//p가 왼쪽일때
	if (p > c) {
		return Gear[p][6] != Gear[c][2];
	}
    //p가 오른쪽일때
	else {
		return Gear[p][2] != Gear[c][6];
	}
}

//회전 시키는 함수
void turn(int n, int d) {
	if (d == 1) {
		Gear[n].insert(Gear[n].begin(), Gear[n].back());
		Gear[n].pop_back();
	}
	else {
		Gear[n].push_back(Gear[n].front());
		Gear[n].erase(Gear[n].begin());
	}
}

//state를 반영해야 할듯 bit로
//회전을 처리하는 함수
void doOrder(int n, int d) {
	vector<pair<int, int>> target;
	target.push_back({ n,d });
	int pre = n;
	int preDir = d;

	//오른쪽으로 확인
	for (int i = n; i < 4; i++) {
		if (i == pre) continue;
		//회전하지 않는다면 더 이상 탐색할 필요없음
		if (!chekTrun(pre, i)) break;
		preDir *= -1;
		target.push_back({ i, preDir });
		pre = i;
	}
	pre = n;
	preDir = d;

	//왼쪽으로 확인
	for (int i = n; i >= 0; i--) {
		if (i == pre) continue;
		//회전하지 않는다면 더 이상 탐색할 필요없음
		if (!chekTrun(pre, i)) break;
		preDir *= -1;
		target.push_back({ i, preDir });
		pre = i;
	}

	//회전 수행
	for (auto iter : target) {
		turn(iter.first, iter.second);
	}
}

void input() {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 8; j++) {
			char a;
			cin >> a;
			Gear[i][j] = a - '0';
		}
	}

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int a, b;
		cin >> a >> b;
		order.push_back({ a-1,b });
	}
}


void solution() {
	for (auto iter : order) {
		int gear = iter.first;
		int dir = iter.second;
		doOrder(gear, dir);
	}
	int sol = findScore();
	cout << sol;
}

int main() {
	input();
	solution();
}