백준 Gold 5 톱니바퀴

톱니바퀴 (백준 Gold 5)

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

8 개의 ‘극’을 가진 4개의 톱니바퀴 정보가 주어지고
특정 톱니바퀴를 시계/반시계 로 회전시키는 t개의 정보가 주어질때
마지막 회전 이후, 톱니바퀴들의 위쪽에 있는 것이 S극이라면
pow(2, 각 톱니바퀴의 번호(0~3)) 를 더하여 반환하는 문제

• 톱니바귀 정보
  0 : N극
  1 : S극
  (시계 방향으로 주어짐)
  

• 회전 정보
  2개의 정수로
  첫 정수가 ‘회전시킬 톱니바퀴 번호’
  두번째가 ‘회전 방향’
  (1이면 시계, -1이면 반시계)
  

풀이 방법

벡터 내부를 실제로 회전시키는 방식은 비효율적이므로
그냥 Top을 가리키는 인덱스를 사용하기로 하였다
(Queue로 해볼까도 싶었지만,
Left,Right에 해당하는 수치에도 접근이 가능해야 해야 했기에)

• 그렇기에 맨 위의 인덱스를 저장하는 vector 사용
  

• 이후 원본 값 벡터를 별도로 저장
  

• 이후, 인덱스를 0~7 사이에 두며 인덱스의 범위를 Clamp한다
  (0에서 -1이 되면, 7로, 7에서 8이 되면 0으로)
  (엄밀히 말하면 Clamp와는 조금 다르지만)
  

• 추가로 유의할 점은
  톱니바퀴 자체의 회전은 맨 마지막에 하는 것이다
  (먼저 회전시키면, 옆의 톱니바퀴와 비교하기 힘들어짐)
  동시에, 방향을 둘로 나누어 재귀를 태우는 방식을 사용하였다
  

제출 코드

#include<iostream>
#include<string>
#include<vector>
#include<math.h>

using namespace std;

int getValue(vector<vector<int>>& vv, vector<int>& iv)
{
	int res = 0;

	for (int i = 0; i < 4; i++)
	{
		if (vv[i][iv[i]] == 1)
		{
			res += pow(2, i);
		}
	}

	return res;
}

int getRightIndex(int idx, int value)
{
	int ret = idx + value;
	if (ret >= 8)
		ret %= 8;
	else if (ret < 0)
		ret = 8 + ret;

	return ret;
}

int getLeftValue(vector<vector<int>>& vv, int gearNum, int startIdx)
{
	int tIdx = getRightIndex(startIdx, -2);
	return vv[gearNum][tIdx];
}

int getRightValue(vector<vector<int>>& vv, int gearNum, int startIdx)
{
	int tIdx = getRightIndex(startIdx, 2);
	return vv[gearNum][tIdx];
}

void Spin(vector<vector<int>>& vv, vector<int>& iv, int nowGear, int dir, bool bRight)
{
	if (nowGear >= 4 || nowGear < 0)
		return;

	if (bRight)
	{
		if (nowGear < 3 &&
			getRightValue(vv, nowGear, iv[nowGear]) != getLeftValue(vv, nowGear + 1, iv[nowGear + 1]))
		{
			Spin(vv, iv, nowGear + 1, -dir, bRight);
		}
	}
	else
	{
		if (nowGear > 0 &&
			getLeftValue(vv, nowGear, iv[nowGear]) != getRightValue(vv, nowGear - 1, iv[nowGear - 1]))
		{
			Spin(vv, iv, nowGear - 1, -dir, bRight);
		}
	}

	iv[nowGear] = getRightIndex(iv[nowGear], dir);
}

void StartSpin(vector<vector<int>>& vv, vector<int>& iv, int nowGear, int dir)
{
	if (nowGear < 3 &&
		getRightValue(vv, nowGear, iv[nowGear]) != getLeftValue(vv, nowGear + 1, iv[nowGear + 1]))
		Spin(vv, iv, nowGear + 1, -dir, true);

	if (nowGear > 0 &&
		getLeftValue(vv, nowGear, iv[nowGear]) != getRightValue(vv, nowGear - 1, iv[nowGear - 1]))
		Spin(vv, iv, nowGear - 1, -dir, false);

	iv[nowGear] = getRightIndex(iv[nowGear], dir);
}

int main()
{
	// 시작 위치를 가리키는 녀석을 기준으로 순회하는 것을 추천함
	// 그리고 시작 위치만 이동시키면 비교할 수 있음
	vector<vector<int>> valueVec;
	for (int i = 0; i < 4; i++)
	{
		valueVec.push_back(vector<int>());
		string t;
		cin >> t;
		for (int j = 0; j < 8; j++)
		{
			valueVec[i].push_back(t[j] - '0');
		}
	}

	int t;
	cin >> t;
	vector<int> topIdx(4, 0);
	while (t > 0)
	{
		int gearNum, dir;
		cin >> gearNum >> dir;
		gearNum--;
		StartSpin(valueVec, topIdx, gearNum, -dir);

		t--;
	}

	cout << getValue(valueVec, topIdx);

	return 0;
}

결과

문제를 2번정도 잘못보았다

• 무조건 0번 톱니바퀴에서 시작하며
  회전량 + 방향 이 제공되는 줄 알았다
  

• 정보가 ‘반시계’로 주어진줄 알았기에
  시계/반시계 에 대한 코드적인 혼란이 있었다
  

해당하는 부분들을 수정하니 통과할 수 있었다