<Baekjoon> #14891 Deque_톱니바퀴 c++

#14891 톱니바퀴

처음에 문제를 보고 쉬운 문제라고 생각했고
톱니바퀴의 상태를 저장하는 벡터를 만들고 옆에 있는 톱니와 맞닿는 톱니의 index를 따로 저장해서 톱니가 움직일 때마다 이 index만 계속 변경해주면 된다고 생각했다.
그런데 그럴 필요 없이 deque를 이용하면 훨씬 편하게 구할 수 있다.

(톱니바퀴의 원형 구조를 그림에 떡하니 그려놓은 거는deque를 사용하라고 그런 것 같다.. 눈치 못 챈 나는 바보)

톱니바퀴를 돌릴 때 비교해야 하는 값은
왼쪽 톱니의 3번째와 가운데 톱니의 7번째 톱니, 가운데 톱니의 3번째와 오른쪽 톱니의 7번째 톱니를 차례대로 비교해가야 한다는 것을 알고 시작한다.

1. deque생성 및 저장

• 4개의 deque를 만들고 입력 값을 저장한다

deque<int> dq[4];

2. 현재 톱니와 양쪽의 톱니 비교

• solution (int idx, int dir) 함수에서는 현재 톱니의 index와 방향 (dir)을 받아와 양쪽 톱니와 비교한다
• 하나의 톱니를 돌리면 그 옆에 톱니들의 N,S극을 비교하여 연쇄적으로 돌려야하기 때문에 톱니를 더이상 돌리지 않아도 될 때까지 반복한다.
• 이때 반드시 visited로 이미 이 지점을 방문했고 톱니가 돌아갈 것이라는 표시를 해준다.
• 3번 톱니가 시계 방향이면 2번톱니는 시계 반대 방향, 1번 톱니는 시계 방향 이렇게 움직여야 하기 때문에 방향을 매번 바꿔준다 (dir*(-1))

	visited[idx] = true;
	int Lidx = idx - 1;
	int Ridx = idx + 1;

    if (Lidx >= 0 && !visited[Lidx] && dq[Lidx][2] != dq[idx][6])
		solution(idx - 1, dir * (-1));
	if (Ridx < 4 && !visited[Ridx] && dq[idx][2] != dq[Ridx][6])
		solution(idx + 1, dir * (-1));

3. 톱니를 돌려야 하는 양 끝단의 톱니부터 돌려준다

• 시계 반대방향으로 돌리는 경우 톱니의 제일 상단 dq[].front() 의 값이 제일 마지막으로 간다.
  

	if (dir == -1) {
		int tmp = dq[idx].front();
		dq[idx].pop_front();
		dq[idx].push_back(tmp);
	}

• 시계 방향으로 돌리는 경우 톱니의 제일 하단 dq[].back()의 값이 제일 앞으로 간다.
  

	else if (dir == 1) {
		int tmp = dq[idx].back();
		dq[idx].pop_back();
		dq[idx].push_front(tmp);
	}

전체 코드

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

deque<int> dq[4];
bool visited[4];

void init() {
	for (int i = 0; i < 4; i++) {
		string c;
		cin >> c;
		for (int j = 0; j < 8; j++) {
			int tmp = c[j]-'0';
			dq[i].push_back(tmp);
		}
	}
}
void turnCog(int idx, int dir) {
	if (dir == -1) {
		int tmp = dq[idx].front();
		dq[idx].pop_front();
		dq[idx].push_back(tmp);
	}
	else if (dir == 1) {
		int tmp = dq[idx].back();
		dq[idx].pop_back();
		dq[idx].push_front(tmp);
	}
}

void solution(int idx, int dir) {
	visited[idx] = true;
	int Lidx = idx - 1;
	int Ridx = idx + 1;

	if (Lidx >= 0 && !visited[Lidx] && dq[Lidx][2] != dq[idx][6])
		solution(idx - 1, dir * (-1));
	if (Ridx < 4 && !visited[Ridx] && dq[idx][2] != dq[Ridx][6])
		solution(idx + 1, dir * (-1));
	turnCog(idx, dir);
}

int main() {
	init();
	int testCase;
	cin >> testCase;
	while (testCase--) {
		int idx, dir;
		cin >> idx >> dir;
		solution(idx - 1, dir);
		memset(visited, false, sizeof(visited));
	}
	int answer = 0;
	for (int i = 0; i < 4; i++) {
		if (dq[i][0])
			answer += pow(2, i);
	}
	cout << answer << endl;
	return 0;
}