BOJ 14891 - 톱니바퀴

14891번: 톱니바퀴 (acmicpc.net)

14891번: 톱니바퀴

 

접근 방법

처음 문제를 잘못 해석했다.

톱니바퀴를 돌리고 나서, 맞닿는 부분끼리 비교하는 것으로 했지만

문제에선 먼저 비교를 다 한 후에, 돌리는 것으로 문제가 작성이 되어 있었다.

 

문제는 쉽게 해결할 수 있다.

 

톱니바퀴가 4개, 각 톱니바퀴의 바퀴상태가 8개 이므로 브루트포스를 이용하여 모두 확인하는 방향으로 구현했다.

DFS처럼 재귀를 이용하여, 옆 톱니바퀴와 비교하는 식으로 진행하였다.

이 과정에서 비교 후에 톱니바퀴를 돌려야하므로, 후위표기법처럼 재귀함수 뒤에 Rotate하는 함수가 오도록 배치하였다.

 

코드

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<cstring>

#define MAX 100002
#define INF 100002

using namespace std;

int n;
int gear[5][9];
int k; // 회전 횟수

vector<pair<int, int>> rotates;
// 톱니바퀴 번호, 회전 방향 (1: 시계, -1: 반시계)
// 맞닺는 부분 : 2, 6

void rotate_left(int idx);
void rotate_right(int idx);
void rotateStart(int before, int idx, int direction);
void calcScore();

/*
맞닿는 부분 먼저 비교 후, 돌리기
*/
void rotateStart(int before, int idx, int direction) {
	if (idx < 0 || idx >= 4)	return;
	// 오른쪽일때, 6번과 2번
	if (before < idx) {

		// 다르면 반대방향 회전
		if (gear[before][2] != gear[idx][6]) {
			
			if (direction == 1) {
				rotateStart(idx, idx + 1, -1);
				rotate_left(idx);
				
			}
			else {
				rotateStart(idx, idx + 1, 1);
				rotate_right(idx);
				
			}
		}
	}
	// 왼쪽일때
	else if (before > idx) {
		// 다르면 반대방향 회전
		if (gear[before][6] != gear[idx][2]) {
			if (direction == 1) {
				rotateStart(idx, idx - 1, -1);
				rotate_left(idx);
				
			}
			else {
				rotateStart(idx, idx - 1, 1);
				rotate_right(idx);
				
			}
		}
	}
	else {
		if (direction == 1) {
			
			rotateStart(idx, idx + 1, 1);
			rotateStart(idx, idx - 1, 1);
			rotate_right(idx);
		}
		else {
			
			rotateStart(idx, idx + 1, -1);
			rotateStart(idx, idx - 1, -1);
			rotate_left(idx);
		}
	}
}

void rotate_left(int idx) {
	// 0, 0 = 1, 1 = 2
	int tmp = gear[idx][0];
	for (int i = 0; i < 7; i++) {
		gear[idx][i] = gear[idx][i + 1];
	}
	gear[idx][7] = tmp;
}
void rotate_right(int idx) {
	int tmp = gear[idx][7];
	for (int i = 7; i > 0; i--) {
		gear[idx][i] = gear[idx][i - 1];
	}
	gear[idx][0] = tmp;
}

void calcScore() {
	int sum = 0;
	for (int i = 0; i < 4; i++) {
		//cout << gear[i][0] << ' ';
		sum += (gear[i][0] * pow(2,i));
		
	}

	cout << sum;
}

int main() {
	cin.tie(NULL); ios_base::sync_with_stdio(false);
	for (int i = 0; i < 4; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < 8; j++) {
			gear[i][j] = (int)(str[j] - '0');
		}
	}

	cin >> k;
	for (int i = 0; i < k; i++) {
		int a, b;
		cin >> a >> b;
		rotateStart(a-1,a-1,b);
	}

	calcScore();
}