BOJ_14 : 톱니바퀴

👉 문제링크

14891번: 톱니바퀴

---

---

🔸 문제 분석 🔸

• 문제가 좀 길었지만 어려운 조건은 아니다. 4가지 톱니가 있는데, 그 중 하나를 돌렸을때 다른 톱니 상태가 어떻게 변하는지 구하면 된다.
• 각 톱니 상태는 vector 를 쓰면 될 것 같고, 옆 톱니에게 영향을 주는 것은 마치 BFS의 원리와 비슷한 것 같아서 queue를 사용했더니 쉽게 풀렸다.

🔸 코드 🔸

#include<iostream>
#include<string>
#include<vector>
#include<queue>

using namespace std;

void turn(vector<int>& top, int& direction) {
	int temp;
    	// turn right
	if (direction == 1) {	
		temp = top[7];
		for (int i = 7; i > 0; i--) {
			top[i] = top[i - 1];
		}
		top[0] = temp;
	}
    	// turn left
	else {					
		temp = top[0];
		for (int i = 0; i < 7; i++) {
			top[i] = top[i + 1];
		}
		top[7] = temp;
	}
}

int main(void) {

	string status;
	vector<vector<int>>top(4, vector<int>(8));

	for (int i = 0; i < 4; i++)
	{
		cin >> status;
		for (int j = 0; j < 8; j++)
		{
			top[i][j] = status[j] - '0';
		}
	}

	int K, Tnum, direction;
	cin >> K;
	queue<int> q;

	for (int i = 0; i < K; i++)
	{
		int flag[4] = { 0 };

		cin >> Tnum >> direction;
		q.push(Tnum - 1);
		flag[Tnum - 1] = direction;

		while (!q.empty()) {
			int now = q.front();
			int left = top[now][6];
			int right = top[now][2];

			turn(top[now], flag[now]);
			
			if (now - 1 >= 0) {		// 왼쪽 톱니바퀴 존재
            		// 왼쪽 톱니바퀴가 아직 돌아가지 않았고, 접점의 극이 반대
				if (flag[now - 1] == 0 && top[now - 1][2] != left) { 
					q.push(now - 1);
					flag[now - 1] = flag[now] * -1;
				}
			}
			if (now + 1 <= 3) {		// 오른쪽 톱니바퀴 존재
            		// 오른쪽 톱니바퀴가 아직 돌아가지 않았고, 접점의 극이 반대
				if (flag[now + 1] == 0 && top[now + 1][6] != right) { 
					q.push(now + 1);
					flag[now + 1] = flag[now] * -1;
				}
			}
			q.pop();
		}
	}

	int answer = 0;

	if (top[0][0] == 1) answer += 1;
	if (top[1][0] == 1) answer += 2;
	if (top[2][0] == 1) answer += 4;
	if (top[3][0] == 1) answer += 8;

	cout << answer;

	return 0;
}

🔸 코드 해석 🔸

• 톱니의 상태는 vector 의 중첩을 이용했고, 옆 톱니에게 영향을 주는 것은 queue로 구현했다.
• queue의 사용에 빠지지 않는... 방문 여부를 판단하는 리스트 flag로 방향을 저장했다.
• 톱니의 회전은 turn 함수를 만들어서 톱니 번호와 방향을 매개변수로 받아 돌리는 방식으로 구현했다.

---

🔸 end 🔸

• 문제 이해와 풀이 시간이 거의 비슷하게 걸린 것 같다.
• 골드 5 문제였지만, vector와 queue사용으로 생각보다 아주 쉽게 풀렸다.
• 자료형을 잘 선택한 경우인 것 같다.