[백준][삼성 SW 역량 테스트][Silver 1][C++] 14891 톱니바퀴

문제

백준 삼성 SW 역량 테스트 기출 문제 - 14891 톱니바퀴 (Silver 1)

14891번: 톱니바퀴

 

---

문제 풀이

접근 방식

주어진 규칙대로 톱니바퀴를 회전시킬 때, 최종 톱니바퀴의 상태를 구하는 문제이다.

한 톱니바퀴가 회전할 때 옆의 톱니바퀴와 맞닿은 톱니의 극이 다른 경우,

옆의 톱니바퀴는 반대방향으로 회전하게 된다. 이를 고려하여 톱니바퀴를 회전시켜주었다.

 

우선, 회전시킬 톱니바퀴의 주변으로 퍼져나가며 함께 회전시킬 바퀴들을 탐색을 해야하기 때문에,

BFS 함수를 만들어 탐색을 수행하였다.

이후, 시계 방향으로 회전하는 톱니바퀴는 맨 마지막의 값을 push_front한 후에 제거하고,

시계 반대 방향으로 회전하는 톱니바퀴는 맨 처음의 값을 push_back 한 후에 제거하여 회전을 구현하였다.

 

---

풀이 코드 - C++

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

vector<deque<int> > cogwheel(4, deque<int>(8));

void BFS(int start, int dir) {
	// 톱니바퀴가 이동할 방향 구하기
	int move[4] = { 0 };
	move[start] = dir;
	queue<pair<int,int> > q;
	q.push({ start, dir });
	while (!q.empty()) {
		int now = q.front().first;
		int dir = q.front().second;
		q.pop();
		if (now - 1 >= 0 && move[now - 1] == 0) {
			if (cogwheel[now][6] != cogwheel[now - 1][2]) {
				move[now - 1] = -dir;
				q.push({ now - 1,-dir });
			}
		}
		if (now + 1 < 4 && move[now + 1] == 0) {
			if (cogwheel[now][2] != cogwheel[now + 1][6]) {
				move[now + 1] = -dir;
				q.push({ now + 1,-dir });
			}
		}
	}

	// 톱니바퀴 이동
	for (int i = 0; i < 4; i++)	{
		if (move[i] == 1) {
			cogwheel[i].push_front(cogwheel[i][7]);
			cogwheel[i].pop_back();
		}
		else if (move[i] == -1) {
			cogwheel[i].push_back(cogwheel[i][0]);
			cogwheel[i].pop_front();
		}
	}
}

int main() {
	for (int i = 0; i < 4; i++) {
		string a;
		cin >> a;
		for (int j = 0; j < 8; j++) {
			if (a[j] == '1')
				cogwheel[i][j] = 1;
		}
	}
	int K;
	cin >> K;
	for (int i = 0; i < K; i++) {
		int a, b;
		cin >> a >> b;
		BFS(a - 1, b);
	}

	int answer = 0;
	for (int i = 0; i < 4; i++) {
		if (cogwheel[i][0] == 1)
			answer += pow(2, i);
	}
	cout << answer;
}

실행 결과

실행 결과 : 통과 (0ms)