[백준 C++] 14891 톱니바퀴

문제

총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.

이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다.

톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 예를 들어, 아래와 같은 경우를 살펴보자.

두 톱니바퀴의 맞닿은 부분은 초록색 점선으로 묶여있는 부분이다. 여기서, 3번 톱니바퀴를 반시계 방향으로 회전했다면, 4번 톱니바퀴는 시계 방향으로 회전하게 된다. 2번 톱니바퀴는 맞닿은 부분이 S극으로 서로 같기 때문에, 회전하지 않게 되고, 1번 톱니바퀴는 2번이 회전하지 않았기 때문에, 회전하지 않게 된다. 따라서, 아래 그림과 같은 모양을 만들게 된다.

위와 같은 상태에서 1번 톱니바퀴를 시계 방향으로 회전시키면, 2번 톱니바퀴가 반시계 방향으로 회전하게 되고, 2번이 회전하기 때문에, 3번도 동시에 시계 방향으로 회전하게 된다. 4번은 3번이 회전하지만, 맞닿은 극이 같기 때문에 회전하지 않는다. 따라서, 아래와 같은 상태가 된다.

톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.

다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

출력

총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.

• 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
• 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
• 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
• 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

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

vector VS deque 개념정리

vector는 원소가추가될때마다 메모리 재할당후, 메모리를 복사하나,
deque는 메모리가부족할때만 일정크기의 새로운 메모리블럭을 할당받음.(메모리복사할필요X)
따라서 삽입삭제가 빈번하거나 회전이필요할시 deque를, 이외에는 vector가 성능이 더 좋다.

풀이(에러 개선과정)

처음에 큐로 회전을 구현하면서 짜다가 방향헷갈려서 몇시간날려먹고,
톱니바퀴 4개의 각각 맞닿은 3군데가 회전이가능한지를 체크한 gaps[3] 배열을
2 x 2 x 2(각각 회전이 되냐 안되냐를 동시에 3번정해지는 경우) = 8인데
이것을 줄여서쓰다가 꼬여서 또 몇시간날렸다.

그후, deque로 데이터구조를 바꾸고, deque의 front가 12시방향이되도록, 처음에 데이터를 back에서 부터 넣었다.

데크의 구조는 이러한데, 여기서 back에 원소를 넣으면 하나씩 front로 밀려나게된다.

반대로 front에 넣으면또 back쪽으로 원소가밀려나고,
중간의 원소를 삭제하면, 앞뒤 그룹중 더 적은 그룹을 큰그룹쪽으로 당긴다.

작성한 코드는 되게 반복노가다인데 가독성은 좋다고생각한다..

#define _CRT_SECURE_NO_WARNINGS 
#include <bits/stdc++.h>
using namespace std;
deque<int> gear[4];
int K = 0;
vector<pair<int, int>> rot; //회전시킨방법들
bool gaps[3] = { false, };	//3구간이 각각 돌아가는가?
int cnt = 0;

void gear_r(int gearNum, int r);
int gear_p(int gearNum, bool right);
void cw(int gearNum);
void ccw(int gearNum);
void rotate(int n, int r);
void machine();
void printAll();

void cw(int gearNum) { //시계방향으로 회전
	int temp = gear[gearNum].back();
	gear[gearNum].pop_back();
	gear[gearNum].push_front(temp);
}

void ccw(int gearNum) { //반시계방향으로 회전
	int temp = gear[gearNum].front();
	gear[gearNum].pop_front();
	gear[gearNum].push_back(temp);
}

//기어의 오른쪽, 왼쪽(맞닿는 부분)을 출력한다.
int gear_p(int gearNum, bool right) { 
	int res = 0;
	if (right) { //오른쪽 정보를출력
		//3번째 즉 2번인덱스값
		res = gear[gearNum][2];
	}else{ //왼쪽정보를 출력
		//7번째, 즉 6번인덱스값
		res = gear[gearNum][6];
	}
	return res;
}

void rotate(int n, int r) { //n번기어를 r방향으로 돌림
	for (int i = 0; i < 3; i++) //초기화
		gaps[i] = false;
	//세 구간에서 회전이 일어나는가
	if (gear_p(0, true) != gear_p(1, false)) gaps[0] = true;
	if (gear_p(1, true) != gear_p(2, false)) gaps[1] = true;
	if (gear_p(2, true) != gear_p(3, false)) gaps[2] = true;

	//n에따라 기어상태들을 변화
	if (n == 1) {
		if (gaps[0] == true &&
			gaps[1] == true &&
			gaps[2] == true) {
			gear_r(2, r * -1);
			gear_r(3, r);
			gear_r(4, r * -1);
		}
		else if (gaps[0] == true &&
			gaps[1] == true &&
			gaps[2] == false) {
			gear_r(2, r * -1);
			gear_r(3, r);
		}
		else if (gaps[0] == true &&
			gaps[1] == false &&
			gaps[2] == true) {
			gear_r(2, r * -1);
		}
		else if (gaps[0] == false &&
			gaps[1] == true &&
			gaps[2] == true) {
			//pass
		}
		else if (gaps[0] == false &&
			gaps[1] == false &&
			gaps[2] == true) {
			//pass
		}
		else if (gaps[0] == true &&
			gaps[1] == false &&
			gaps[2] == false) {
			gear_r(2, r * -1);
		}
		else if (gaps[0] == false &&
			gaps[1] == true &&
			gaps[2] == false) {
			//pass
		}
		else if (gaps[0] == false &&
			gaps[1] == false &&
			gaps[2] == false) {
			//pass
		}
		gear_r(1, r);
	}
	else if (n == 2) {
		if (gaps[0] == true &&
			gaps[1] == true &&
			gaps[2] == true) {
			gear_r(1, r * -1);
			gear_r(3, r * -1);
			gear_r(4, r);
		}
		else if (gaps[0] == true &&
			gaps[1] == true &&
			gaps[2] == false) {
			gear_r(1, r * -1);
			gear_r(3, r * -1);
		}
		else if (gaps[0] == true &&
			gaps[1] == false &&
			gaps[2] == true) {
			gear_r(1, r * -1);
		}
		else if (gaps[0] == false &&
			gaps[1] == true &&
			gaps[2] == true) {
			gear_r(3, r * -1);
			gear_r(4, r);
		}
		else if (gaps[0] == false &&
			gaps[1] == false &&
			gaps[2] == true) {
			//pass
		}
		else if (gaps[0] == true &&
			gaps[1] == false &&
			gaps[2] == false) {
			gear_r(1, r * -1);
		}
		else if (gaps[0] == false &&
			gaps[1] == true &&
			gaps[2] == false) {
			gear_r(3, r * -1);
		}
		else if (gaps[0] == false &&
			gaps[1] == false &&
			gaps[2] == false) {
			//pass
		}
		gear_r(2, r);
	}
	else if (n == 3) {
		if (gaps[0] == true &&
			gaps[1] == true &&
			gaps[2] == true) {
			gear_r(1, r);
			gear_r(2, r * -1);
			gear_r(4, r * -1);
		}
		else if (gaps[0] == true &&
			gaps[1] == true &&
			gaps[2] == false) {
			gear_r(1, r);
			gear_r(2, r * -1);
		}
		else if (gaps[0] == true &&
			gaps[1] == false &&
			gaps[2] == true) {
			gear_r(4, r * -1);
		}
		else if (gaps[0] == false &&
			gaps[1] == true &&
			gaps[2] == true) {
			gear_r(2, r * -1);
			gear_r(4, r * -1);
		}
		else if (gaps[0] == false &&
			gaps[1] == false &&
			gaps[2] == true) {
			gear_r(4, r * -1);
		}
		else if (gaps[0] == true &&
			gaps[1] == false &&
			gaps[2] == false) {
			//pass
		}
		else if (gaps[0] == false &&
			gaps[1] == true &&
			gaps[2] == false) {
			gear_r(2, r * -1);
		}
		else if (gaps[0] == false &&
			gaps[1] == false &&
			gaps[2] == false) {
			//pass
		}
		gear_r(3, r);
	}
	else if (n == 4) {
		if (gaps[0] == true &&
			gaps[1] == true &&
			gaps[2] == true) {
			gear_r(1, r * -1);
			gear_r(2, r);
			gear_r(3, r * -1);
		}
		else if (gaps[0] == true &&
			gaps[1] == true &&
			gaps[2] == false) {
			//pass
		}
		else if (gaps[0] == true &&
			gaps[1] == false &&
			gaps[2] == true) {
			gear_r(3, r * -1);
		}
		else if (gaps[0] == false &&
			gaps[1] == true &&
			gaps[2] == true) {
			gear_r(2, r);
			gear_r(3, r * -1);
		}
		else if (gaps[0] == false &&
			gaps[1] == false &&
			gaps[2] == true) {
			gear_r(3, r * -1);
		}
		else if (gaps[0] == true &&
			gaps[1] == false &&
			gaps[2] == false) {
			//pass
		}
		else if (gaps[0] == false &&
			gaps[1] == true &&
			gaps[2] == false) {
			//pass
		}
		else if (gaps[0] == false &&
			gaps[1] == false &&
			gaps[2] == false) {
			//pass
		}
		gear_r(4, r);
	}
}

void gear_r(int gearNum, int r) {
	int num = gearNum - 1;
	if (num < 0 || num > 3) //기어범위가 잘못된경우
		return;

	//기어를 해당방향으로돌림
	if (r == 1) {
		//시계방향
		cw(num);
	}
	else if (r == -1) {
		//반시계방향
		ccw(num);
	}
}

void machine() { //회전시킨 정보를 모두 실행
	for (int i = 0; i < K; i++) {
		//i번째 요소(회전시킨기어, 방향)를 꺼냄
		int n = rot[i].first;
		int r = rot[i].second;
		rotate(n, r);
	}
}

void printAll() {
	cnt++;
	int res = 0;
	res += 1 * gear[0].front();
	res += 2 * gear[1].front();
	res += 4 * gear[2].front();
	res += 8 * gear[3].front();
	
	printf("%d\n", res);
}

int main(void) {
	int temp=0, temp2=0;
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 8; j++) { //기어상태 저장
			scanf("%1d", &temp);
			gear[i].push_back(temp); //거꾸로넣어야 처음원소가 front가됨
		}
	}
	scanf("%d", &K);
	for (int i = 0; i < K; i++) { //회전시킨정보를 저장
		scanf("%d%d", &temp, &temp2);
		//회전시킨기어번호, 방향 
		rot.push_back({ temp, temp2 });
	}
	machine();
	printAll();

	return 0;
}

무려 약 300줄에 달하는 코드이다.. 재귀구조를 이용하면 더 간략하게 짤 수 있었을것같다.