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

문제 링크

---

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

14891번: 톱니바퀴

 

문제 접근

---

 주어지는 톱니 바퀴는 반시계방향, 시계방향으로 회전할 수 있으며, 옆에 다른 톱니바퀴의 회전에 영향을 줄 수 있다. 위의 톱니 바퀴를 수로 표현하면 10101111입니다. 각 숫자를 원형큐로 구현하여 회전을 쉽게 구현할 수 있습니다. 저는 원형큐가 익숙하지 않아서 보이는 그대로 비트 연산을 통해 구현하였습니다. 따라서 비트 연산으로 설명을 할 것인데, 리스트로 구현한 코드도 같이 올리도록 하겠습니다.

 

양 옆의 톱니 바퀴의 회전을 고려하기 전에, 기본 회전 코드를 먼저 짜는게 좋습니다.

 

<시계 방향 회전>

10101111 -> 01010111 (>> 연산만 한 결과 temp_bit = 1) -> 11010111 (temp_bit을 2^7로 올린 결과)

temp_bit = 1

>> 연산과 2^0 자릿수의 1을 다시 2^7으로 올리는 코드 구현

if (direct == 1) { // 시계 방향(오른쪽으로, 7번째 비트 저장 필요)
		temp_bit = get_bit(g, 7) << 7;
		gear = gear >> 1;
		gear |= temp_bit;
	}

<반시계 방향 회전>

10101111 -> 01011110 (<< 연산만 한 결과, temp_bit = 1) -> 01011111 (temp_bit을 2^0으로 올린 결과)

<< 연산과 2^7 자릿수를 다시 2^0으로 내리는 코드 구현

else if (direct == -1) { // 반시계 방향(왼쪽으로, 0번째 비트 저장 필요)
		temp_bit = get_bit(g, 0);
		gear = gear << 1;
		gear |= temp_bit;
	}

 

여기서 get_bit(g, idx)는 g라는 2진수 값에서 idx번째 자릿수를 얻는 연산입니다. 코드는 아래와 같습니다.

int get_bit(int g, int idx) {
	int temp = 1 << (7 - idx);
	int gear_bit = (gears[g] & temp);
	while (gear_bit > 1) {
		gear_bit = gear_bit >> 1;
	}
	return gear_bit;
}

 

자, 이제 g번째 바퀴를 회전시킬 때, 맞닿은 톱니 바퀴의 값이 반대인 경우, 해당 바퀴도 반대 방향으로 회전해주는 코드를 작성해볼게요.

 

i번 바퀴로 설명하겠습니다.

1. (i - 1)번 바퀴의 2번 비트가 (i)번 바퀴의 6번 비트와 다르다면 회전

2. (i + 1)번 바퀴의 6번 비트가 (i)번 바퀴의 2번 비트와 다르다면 회전

이 두 가지 조건에 visit 배열을 통한 바퀴 방문 여부, (i - 1), (i + 1) 인덱스 참조가 가능한지의 조건만 더해지면 재귀 함수를 완성할 수 있습니다. 설명과 아래 코드를 비교해보세요.

// g번째 바퀴의 g_idx와 ng번째 바퀴의 ng_idx가 같으면 true, 아니면 false
bool is_samebit(int g, int g_idx, int ng, int ng_idx) {
	return get_bit(g, g_idx) == get_bit(ng, ng_idx);
}

int rotate_gear(int g, int d) {
	visit[g] = 1;
	int rotated_gear = rotate(g, d);
	// 왼쪽 기어 확인
	if ((g - 1) >= 0 && !visit[g - 1] && !is_samebit(g, 6, g - 1, 2))
		rotate_gear(g - 1, d * -1);
	if ((g + 1) < NUM_GEARS && !visit[g + 1] && !is_samebit(g, 2, g + 1, 6))
		rotate_gear(g + 1, d * -1);
	gears[g] = rotated_gear;
	return 0;
}

중요한 점은 회전을 먼저 하고 검사를 하면 안된다는 것입니다. 회전하기 전에 각 맞닿은 비트를 검사해놓고, 회전은 나중에 해야합니다. 문제를 잘 읽어보시면 이해가 가실겁니다.

 

비트 연산이 햇갈리시면 #include <bitset>을 하셔서 bitset<8>(gears[0])를 이용해서 직접 비트를 출력해보시면 도움이 많이 됩니다.

 

소스 코드

---

<비트로 구현>

#include <bitset>
#include <cstring>
#include <iostream>
#include <algorithm>
#define NUM_GEARS 4
using namespace std;
int gears[NUM_GEARS], K, visit[NUM_GEARS];

int get_bit(int g, int idx) {
	int temp = 1 << (7 - idx);
	int gear_bit = (gears[g] & temp);
	while (gear_bit > 1) {
		gear_bit = gear_bit >> 1;
	}
	return gear_bit;
}

int rotate(int g, int direct) {
	int temp_bit, gear = gears[g];
	if (direct == 1) { // 시계 방향(오른쪽으로, 7번째 비트 저장 필요)
		temp_bit = get_bit(g, 7) << 7;
		gear = gear >> 1;
		gear |= temp_bit;
	}
	else if (direct == -1) { // 반시계 방향(왼쪽으로, 0번째 비트 저장 필요)
		temp_bit = get_bit(g, 0);
		gear = gear << 1;
		gear |= temp_bit;
	}
	return gear;
}

// g번째 바퀴의 g_idx와 ng번째 바퀴의 ng_idx가 같으면 true, 아니면 false
bool is_samebit(int g, int g_idx, int ng, int ng_idx) {
	return get_bit(g, g_idx) == get_bit(ng, ng_idx);
}

int rotate_gear(int g, int d) {
	visit[g] = 1;
	int rotated_gear = rotate(g, d);
	if ((g - 1) >= 0 && !visit[g - 1] && !is_samebit(g, 6, g - 1, 2))
		rotate_gear(g - 1, d * -1); // 왼쪽 기어 확인
	if ((g + 1) < NUM_GEARS && !visit[g + 1] && !is_samebit(g, 2, g + 1, 6))
		rotate_gear(g + 1, d * -1); // 오른쪽 기어 확인
	gears[g] = rotated_gear;
	return 0;
}

int get_score() {
	int ret = 0, bit, coefficient = 1;
	for (int i = 0; i < NUM_GEARS; ++i) {
		bit = get_bit(i, 0); // 0번째 비트 = 12시 방향의 비트
		ret += coefficient * bit;
		coefficient *= 2;
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	char a;
	for (int i = 0; i < NUM_GEARS; ++i) {
		for (int j = 0; j < 8; ++j) {
			cin >> a;
			a -= '0';
			gears[i] |= (a << (7 - j));
		}
	}
	cin >> K;
	int g, d;
	for (int k = 0; k < K; ++k) {
		memset(visit, 0, sizeof(visit));
		cin >> g >> d;
		rotate_gear(g - 1, d);
	}
	cout << get_score();
	return 0;
}

 

<리스트로 구현>

#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define NUM_GEARS 4
using namespace std;
int gears[NUM_GEARS][8], K, visit[NUM_GEARS];
vector<pair<int, int>> ops;

// i번째 톱니바퀴를 d방향으로 회전
void rotate(int i, int d) {
	int temp;
	if (d == 1) { // 시계방향, 우측
		temp = gears[i][7];
		for (int j = 7; j >= 1; --j)
			gears[i][j] = gears[i][j - 1];
		gears[i][0] = temp;
	}
	else if (d == -1) { // 반시계방향, 좌측
		temp = gears[i][0];
		for (int j = 0; j + 1 < 8; ++j)
			gears[i][j] = gears[i][j + 1];
		gears[i][7] = temp;
	}
}

// g번째 바퀴의 gi번째 비트와 ng번째 바퀴의 ngi번째 비트를 비교한다.
bool is_different(int g, int gi, int ng, int ngi) {
	return gears[g][gi] != gears[ng][ngi]; // 같으면 true, 다르면 false
}

void check_rotate(int i, int d) {
	visit[i] = 1;
	ops.push_back({ i, d });
	int left = i - 1, right = i + 1;
	//cout << i << "번째 바퀴 => ";
	if (left >= 0) { // 왼쪽이 존재한다면
		//cout << "나의 6번째 값:" << gears[i][6] << " 왼쪽의 2번째 값:" << gears[i][2] << "\n";
		if (!visit[left] && is_different(i, 6, left, 2)) {
			check_rotate(left, d * -1);
		}
	}

	if (right < NUM_GEARS) {
		//cout << "나의 2번째 값:" << gears[i][2] << " 오른쪽의 6번째 값:" << gears[i][6] << "\n";
		if (!visit[right] && is_different(i, 2, right, 6)) {
			check_rotate(right, d * -1);
		}
	}
}

int get_score() {
	int ret = 0, sum_check = 1;
	for (int g = 0; g < NUM_GEARS; ++g) {
		if (gears[g][0] == 1) ret += sum_check;
		sum_check *= 2;
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	char input;
	for (int i = 0; i < NUM_GEARS; ++i)
		for (int j = 0; j < 8; ++j) {
			cin >> input;
			gears[i][j] = input - '0';
		}

	cin >> K;
	int g, d;
	for (int k = 0; k < K; ++k) {
		memset(visit, 0, sizeof(visit));
		cin >> g >> d;
		check_rotate(g - 1, d);
		for (int i = 0; i < ops.size(); ++i) {
			rotate(ops[i].first, ops[i].second);
		}
		ops.clear();
	}
	cout << get_score();
	return 0;
}

개발 환경 : VS2019

질문, 지적 환영합니다.