[BOJ/백준 14891/C++] 톱니바퀴

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

14891번: 톱니바퀴

 

[문제요약]

- 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.

- 이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다.

- 톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다.

- 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다.

- 톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.

- 총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.

• 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
• 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
• 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
• 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

[문제 조건]

- 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.

- 다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 

- 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

- 시간 제한 : 2초

- 메모리 제한 : 512MB

 

[문제 풀이]

이 문제는 어려운 알고리즘 없이 톱니들의 상태를 어떤 형태의 자료구조로 저장할 것인가, 톱니 회전을 어떤식으로 표현할 것인가 이 두가지가 중요한 문제다.

 

필자는 톱니들을 회전시킬때 처음에 vector 랑 string을 이용하여 시계방향이면 맨 뒤에 있는 원소를 앞에 붙히는 형태로 할려고 했는데 두 STL 모두 push_front가 없어서 그냥 deque를 이용하였다.

 

void spinning(int saw_num, int direct)
{
	if (direct == 1)
	{
		saw[saw_num].push_front(saw[saw_num].back());
		saw[saw_num].pop_back();
	}
	else if (direct == -1)
	{
		saw[saw_num].push_back(saw[saw_num].front());
		saw[saw_num].pop_front();
	}
}

위 코드는 톱니 하나만 회전 시키는 코드고

 

아래 코드는 전반적인 시뮬레이션이 돌아가는 코드다.

//1 : 시계, -1 : 반시계
void spin_saw(int saw_num, int direct)
{
	ck[saw_num] = true;
	if (saw_num == 1)
	{
		if (!ck[2] && (saw[2][6] != saw[1][2])) spin_saw(2, -direct);

		spinning(1, direct);
	}
	else if (saw_num == 2)
	{
		if (!ck[1] && (saw[1][2] != saw[2][6])) spin_saw(1, -direct);
		if (!ck[3] && (saw[3][6] != saw[2][2])) spin_saw(3, -direct);

		spinning(2, direct);
	}
	else if (saw_num == 3)
	{
		if (!ck[2] && (saw[2][2] != saw[3][6])) spin_saw(2, -direct);
		if (!ck[4] && (saw[4][6] != saw[3][2])) spin_saw(4, -direct);

		spinning(3, direct);
	}
	else if (saw_num == 4)
	{
		if (!ck[3] && (saw[3][2] != saw[4][6])) spin_saw(3, -direct);

		spinning(4, direct);
	}
}

check배열을 하나 두고 한번 회전시킨 톱니는 다시 회전시키지 않게 해 주었고, 각 톱니별로 양 옆의 각 톱니의 2번 또는 6번 톱니와 비교하면서 서로 다른 극 일때 옆의 톱니도 회전하도록 재귀 방식으로 코드를 작성했다.

 

그리고 최종적으로 구해야되는 정답은 각 톱니의 0번위치에 있는 톱니의 극에 따라 점수가 나오기 때문에 0번위치의 값만 확인하여 답을 구했다.

 

그리 어렵지 않은 문제였지만 구현 문제는 항상 생각해야될게 어느정도 있기 때문에 귀찮은 정도의 문제였던 거 같다.

 

[소스 코드]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <list>
#include <math.h>
#include <map>
#include <queue>
#include <stack>
#define pii pair<int,int>

using namespace std;

vector<deque<int>> saw;
vector<bool> ck;
int K;

void spinning(int saw_num, int direct)
{
	if (direct == 1)
	{
		saw[saw_num].push_front(saw[saw_num].back());
		saw[saw_num].pop_back();
	}
	else if (direct == -1)
	{
		saw[saw_num].push_back(saw[saw_num].front());
		saw[saw_num].pop_front();
	}
}

//1 : 시계, -1 : 반시계
void spin_saw(int saw_num, int direct)
{
	ck[saw_num] = true;
	if (saw_num == 1)
	{
		if (!ck[2] && (saw[2][6] != saw[1][2])) spin_saw(2, -direct);

		spinning(1, direct);
	}
	else if (saw_num == 2)
	{
		if (!ck[1] && (saw[1][2] != saw[2][6])) spin_saw(1, -direct);
		if (!ck[3] && (saw[3][6] != saw[2][2])) spin_saw(3, -direct);

		spinning(2, direct);
	}
	else if (saw_num == 3)
	{
		if (!ck[2] && (saw[2][2] != saw[3][6])) {  spin_saw(2, -direct); }
		if (!ck[4] && (saw[4][6] != saw[3][2])) spin_saw(4, -direct);

		spinning(3, direct);
	}
	else if (saw_num == 4)
	{
		if (!ck[3] && (saw[3][2] != saw[4][6])) spin_saw(3, -direct);

		spinning(4, direct);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	saw.resize(5);
	ck.resize(5);
	for (int i = 1; i <= 4; i++)
	{
		string tmp;
		cin >> tmp;
		for (int j = 0; j < tmp.size(); j++)
			saw[i].push_back(tmp[j] - '0');
	}
	
	cin >> K;
	int saw_num, spin;
	for (int i = 0; i < K; i++)
	{
		for (int j = 0; j <= 4; j++) ck[j] = false;
		cin >> saw_num >> spin;

		spin_saw(saw_num, spin);
	}
	int sum = 0;
	int score = 1;
	for (int i = 1; i <= 4; i++)
	{
		if (saw[i][0] == 1)
			sum += score;
		score *= 2;
	}
	cout << sum;
}

 

굳