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

문제 

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

 

14891번: 톱니바퀴

---

문제이해

 

문제가 그냥 봤을 때는 간단해 보였지만 막상 시도하려고 하니까 어떻게 구현해야 될지 어려운 것 같았습니다.

• 우선 입력으로 4개의 톱니바퀴의 톱니 극을 받고 이후 회전 횟수와 회전 기어, 방향을 입력 받습니다.
• 각각의 회전에 대한 변화를 구현해야 됩니다.
• 출력은 생각보다 간단하게 각 톱니바퀴의 0번째 인덱스의 값만 이용해 계산하면 됩니다.

---

문제해결

 

struct gears
{
	vector<int> magnet;
	gears* leftGear;
	gears* rightGear;
	int way;
	void turnR() {
		int temp = magnet[magnet.size() - 1];
		magnet.pop_back();
		magnet.insert(magnet.begin(), temp);
	}
	void turnL() {
		int temp = magnet[0];
		magnet.erase(magnet.begin());
		magnet.push_back(temp);
	}

	gears(string str) {
		for (char c : str) {
			magnet.push_back(c - '0');
		}
		leftGear = NULL;
		rightGear = NULL;
		way = 0;
	}
};

struct를 사용하여 구현하면 쉬울 것 같다는 느낌이 들어 struct를 통해 톱니바퀴의 톱니 정보와 근처 톱니바퀴 들과의 관계를 정리했습니다.

 

현재 기어의 왼쪽 기어와 오른쪽 기어를 확인하기 위한 포인터를 사용했습니다.

 

기어의 회전에 사용될 turnR() 함수와 turnL() 함수도 넣었습니다.

 

문제의 입력에서 기어의 톱니 정보를 공백 없이 받기 때문에 string을 이용해 받고 이를 한 글자씩 분리해 magnet 벡터에 저장했습니다.

 

way는 시계 방향 회전의 경우 1, 반시계 방향 회전의 경우 -1로 회전하지 않는 상태는 0으로 구별하는데 사용했습니다.

기어 4개의 톱니 정보를 입력받고 각 기어간의 관계를 정리했습니다. gear1과 gear4는 나중에 while문을 사용하여 문제를 풀 생각으로 gear1의 leftGear와 gear4의 rightGear는 NULL 값을 넣었습니다. 이후 정리가 끝난 기어들을 vector에 넣었습니다.

void basic(vector<gears*>& vec) {
	string str;
	cin >> str;
	gears* gear1 = new gears(str);
	cin >> str;
	gears* gear2 = new gears(str);
	cin >> str;
	gears* gear3 = new gears(str);
	cin >> str;
	gears* gear4 = new gears(str);
	gear1->leftGear = NULL;
	gear1->rightGear = gear2;
	gear2->leftGear = gear1;
	gear2->rightGear = gear3;
	gear3->leftGear = gear2;
	gear3->rightGear = gear4;
	gear4->leftGear = gear3;
	gear4->rightGear = NULL;
	vec.push_back(gear1);
	vec.push_back(gear2);
	vec.push_back(gear3);
	vec.push_back(gear4);
}

void start(int G, int W, vector<gears*> gear) {
	if (W == 1) {
		vector<gears*> linked;
		gears* curGear = gear[G - 1];
		curGear->way = 1;
		linked.push_back(curGear);
		while (curGear->leftGear != NULL) {
			if (curGear->magnet[6] != curGear->leftGear->magnet[2]) {
				linked.push_back(curGear->leftGear);
				curGear = curGear->leftGear;
				curGear->way = curGear->rightGear->way * -1;
			}
			else {
				break;
			}
		}
		curGear = gear[G - 1];
		while (curGear->rightGear != NULL) {
			if (curGear->magnet[2] != curGear->rightGear->magnet[6]) {
				linked.push_back(curGear->rightGear);
				curGear = curGear->rightGear;
				curGear->way = curGear->leftGear->way * -1;
			}
			else {
				break;
			}
		}
		for (int i{ 1 }; i <= linked.size(); i++) {
			if (linked[i - 1]->way == 1) {
				linked[i - 1]->turnR();
			}
			else {
				linked[i - 1]->turnL();
			}
		}
	}
	else {
		vector<gears*> linked;
		gears* curGear = gear[G - 1];
		curGear->way = -1;
		linked.push_back(curGear);
		while (curGear->leftGear != NULL) {
			if (curGear->magnet[6] != curGear->leftGear->magnet[2]) {
				linked.push_back(curGear->leftGear);
				curGear = curGear->leftGear;
				curGear->way = curGear->rightGear->way * -1;
			}
			else {
				break;
			}
		}
		curGear = gear[G - 1];
		while (curGear->rightGear != NULL) {
			if (curGear->magnet[2] != curGear->rightGear->magnet[6]) {
				linked.push_back(curGear->rightGear);
				curGear = curGear->rightGear;
				curGear->way = curGear->leftGear->way * -1;
			}
			else {
				break;
			}
		}
		for (int i{ 1 }; i <= linked.size(); i++) {
			if (linked[i - 1]->way == 1) {
				linked[i - 1]->turnR();
			}
			else {
				linked[i - 1]->turnL();
			}
		}
	}
}

1. 회전하기로한 현재 기어를 중심으로 양 옆의 기어에 대해 회전이 전달될 수 있는지 확인하고 회전이 전달될 수 있는 경우 새로 만든 linked 벡터에 넣고 기어를 한 칸씩 전진 할 때마다 해당 기어의 회전 방향을 이전 기어의 회전 방향과 반대가 되도록 했습니다.
2. 이후 linked 벡터에 저장된 기어들에 대해 회전하기로 했던 방향을 확인하고 그 방향과 맞게 기어들을 회전해줬습니다.

void score(vector<gears*> gear) {
	int score{ 0 };
	for (int i{ 1 }; i <= gear.size(); i++) {
		if (gear[i - 1]->magnet[0] == 1) {
			score = score + pow(2, i - 1);
		}
	}
	cout << score;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string str;
	vector<gears*> gears0;
	basic(gears0);
	int n, g, w;
	cin >> n;
	while (n--) {
		cin >> g >> w;
		start(g, w, gears0);
	}
	score(gears0);
}

이후 간단하게 점수를 구하는 함수를 구현했습니다.

---

문제후기

 

struct를 잘 쓰지 못해서 연습해보고 싶어 써봤지만 간단하게 구현하는데 실패한거 같습니다... 그래도 코드를 짜는 동안에 출력이 제대로 나오지 않을까봐 두려워했지만 출력은 정상적으로 나와 다행이라고 생각했습니다...