백준 BOJ 14891 C++ 톱니바퀴

[문제 링크]

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

14891번: 톱니바퀴

 

[문제 풀이]

삼성 기출 시뮬레이션 문제이다.

다른 삼성 기출문제들보다는 난이도가 쉬운 편이라고 생각한다.

톱니바퀴가 4개있고 각 톱니바퀴는 8개의 톱니로 이루어져 있다. 그리고 톱니는 N극(0) 또는 S극(1)으로 이루어져 있다.

각 톱니바퀴는 맞닿은 극이 서로 다르면 회전을 한다. 즉, n번째 톱니바퀴의 2번째 톱니와 n+1번째 톱니바퀴의 6번째 톱니의 극이 서로 다르면 회전을 한다. (톱니는 0부터 시작한다고 가정)

톱니바퀴를 K번 회전시킨 후 조건에 따라 점수를 더한다.

회전 후 각 톱니바퀴의 12시 방향이 S극이면 점수를 더하는데 1번 톱니바퀴는 1점, 2번 톱니바퀴는 2점, 3번 톱니바퀴는 4점, 4번 톱니바퀴는 8점이다. 합산한 점수를 출력하면 된다.

왼쪽 톱니바퀴부터 1번, 2번, 3번, 4번 톱니바퀴이다.

그림과 같은 톱니바퀴가 주어진다면 아래와 같은 숫자로 나타낼 수 있다.

10101111
01111101
11001110
00000010

그 다음엔 K가 주어지고 회전시킬 톱니바퀴 번호와 방향을 입력받는다.

예를 들어 2 1이면 2번 톱니바퀴를 시계방향으로 돌리는 것이다. 1 -1이면 1번 톱니바퀴를 반시계 방향으로 돌리는 것이다.

본인은 문제를 쉽게 풀기 위해 톱니바퀴를 덱으로 선언하여 풀었다.

문제에는 톱니바퀴가 1번부터 시작했지만 본인은 0번부터 시작하였다. 그래서 처음 톱니바퀴 번호를 입력받을 때 -1을 해준다.

회전할 톱니바퀴를 찾기 위해 벡터와 큐를 사용하였다. 또한, 톱니바퀴의 방문 체크를 해주었다.

여기서 중요한 것은 K번 입력받는 톱니바퀴들은 그 방향으로 무조건 회전을 한다. 인접한 톱니바퀴와 극이 같다고 해서 회전을 안 하는 것이 아니다.

그리고 이 문제는 회전하기 전의 상태에서 맞닿은 극이 서로 다르면 서로 다른 방향으로 회전한다. 즉, 입력받은 톱니바퀴를 해당 방향으로 회전시킨 뒤 인접한 톱니바퀴와 맞닿은 극이 서로 다른지를 보는 것이 아니다. 본인은 이 부분에서 문제를 잘못 이해하여 계속 틀렸다.

다시 문제로 돌아와서 처음 입력받는 톱니바퀴 번호와 방향을 큐와 벡터에 넣어준다. 큐는 회전할 톱니바퀴를 찾기 위해서 사용하고, 벡터는 톱니바퀴 정보를 저장하고 실제로 회전시키기 위해 사용한다.

큐가 빌 때까지 반복하면서 회전할 큐를 찾는다. 여기서 톱니바퀴가 0번째가 아닌 경우, 3번째가 아닌 경우로 나뉜다.

0번째가 아닌 경우는 현재 톱니바퀴와 그 왼쪽 톱니바퀴의 맞닿은 극이 서로 다른지, 방문한 톱니바퀴인지 체크한다.

3번째가 아닌 경우는 현재 톱니바퀴와 그 오른쪽 톱니바퀴의 맞닿은 극이 서로 다른지, 방문한 톱니바퀴인지 체크한다.

방문하지 않았고, 맞닿은 극이 서로 다르면 큐와 벡터에 톱니바퀴 번호와 반대 방향(방향 * -1)을 넣어준 뒤 해당 톱니바퀴를 방문 체크해준다.

큐를 통해 회전할 톱니바퀴를 다 찾았으면 반복문을 빠져나오고 벡터에 저장된 회전할 톱니바퀴들을 실제로 회전시킨다.

톱니바퀴는 덱으로 선언했기 때문에 숫자를 앞뒤로 넣고 빼는 것이 쉽다.

시계 방향인 경우 뒤에 숫자를 저장한 뒤 삭제하고 저장한 숫자를 앞에 넣어주면 된다.

반시계 방향인 경우 앞에 숫자를 저장한 뒤 삭제하고 저장한 숫자를 뒤에 넣어주면 된다.

이 작업을 K번 반복한 뒤 마지막에 점수를 더해주면 된다.

K번 반복할 때 방문 체크 배열을 초기화해주고 벡터를 초기화해줘야 한다.

[소스 코드]

#include <bits/stdc++.h>
using namespace std;
int k; //회전 횟수
bool check[4];
deque<int> dq[4]; // 톱니바퀴 상태 저장 및 회전하기 위한 덱

queue<pair<int, int>> q; // 회전할 톱니바퀴를 저장하기 위한 큐
vector<pair<int, int>> v; // 회전할 톱니바퀴들을 실제로 방향에 따라 회전시키기 위한 벡터
void rotate() {
	for (int i = 0; i < v.size(); i++) { // 톱니바퀴 회전 
		int cur_num = v[i].first;
		int cur_d = v[i].second;
		if (cur_d == 1) { // 시계 방향이면
			int tmp = dq[cur_num].back(); // 현재 톱니바퀴의 마지막 숫자를 tmp에 저장
			dq[cur_num].pop_back(); // 현재 톱니바퀴의 마지막 숫자 삭제
			dq[cur_num].push_front(tmp); // 현재 톱니바퀴의 앞에다가 tmp 삽입
		}
		else { // 시계 반대방향이면
			int tmp = dq[cur_num].front(); // 현재 톱니바퀴의 첫번째 숫자를 tmp에 저장
			dq[cur_num].pop_front(); // 현재 톱니바퀴의 첫번째 숫자 삭제
			dq[cur_num].push_back(tmp); // 현재 톱니바퀴의 뒤에다가 tmp 삽입
		}
	}
}
void check_rotate() {
	cin >> k;
	for (int i = 0; i < k; i++) {
		memset(check, false, sizeof(check));
		v.clear();
		int num, d;
		cin >> num >> d;

		num -= 1; // 인덱스를 0부터 시작하기 위해 입력되는 num값에서 -1
		v.push_back({ num,d }); // 처음 입력받는 톱니바퀴와 방향을 푸쉬
		q.push({ num, d }); // 처음 입력받는 톱니바퀴와 방향을 푸쉬
		check[num] = true; // 해당 톱니바퀴 방문체크
		while (!q.empty()) {
			int cur_num = q.front().first; // 현재 톱니바퀴 숫자
			int cur_d = q.front().second; // 회전할 방향
			q.pop();

			if (cur_num != 0) { // 톱니바퀴가 첫번째가 아니라면
				if (dq[cur_num - 1][2] != dq[cur_num][6] && !check[cur_num - 1]) {
					// 왼쪽 톱니바퀴와 극이 다르고 왼쪽 톱니바퀴를 방문하지 않았다면
					q.push({ cur_num - 1, cur_d * -1 }); // 왼쪽 톱니바퀴 번호와 반대 방향을 큐에 푸쉬
					v.push_back({ cur_num - 1, cur_d * -1 }); // 왼쪽 톱니바퀴 번호와 반대 방향을 벡터에 푸쉬
					check[cur_num - 1] = true; // 왼쪽 톱니바퀴 방문 체크
				}
			}
			if (cur_num != 3) { // 톱니바퀴가 마지막이 아니라면
				if (dq[cur_num][2] != dq[cur_num + 1][6] && !check[cur_num + 1]) {
					// 오른쪽 톱니바퀴와 극이 다르고 오른쪽 톱니바퀴를 방문하지 않았다면
					q.push({ cur_num + 1, cur_d * -1 }); // 오른쪽 톱니바퀴 번호와 반대 방향을 큐에 푸쉬
					v.push_back({ cur_num + 1, cur_d * -1 }); // 오른쪽 톱니바퀴 번호와 반대 방향을 벡터에 푸쉬
					check[cur_num + 1] = true; // 오른쪽 톱니바퀴 방문 체크
				}
			}
		}

		rotate();
	}
}

void count() {
	int cnt = 0;
	if (dq[0][0] == 1) cnt += 1;
	if (dq[1][0] == 1) cnt += 2;
	if (dq[2][0] == 1) cnt += 4;
	if (dq[3][0] == 1) cnt += 8;
	cout << cnt;
}
void INPUT() {
	for (int i = 0; i < 4; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < 8; j++) {
			dq[i].push_back(str[j] - '0'); // 톱니바퀴 처음 상태 저장
		}
	}
}
void solve() {
	INPUT();
	check_rotate();
	count();
}
int main() {
	cin.tie(0); ios::sync_with_stdio(0);
	solve();
	return 0;
}