[백준 14891] 톱니바퀴

문제 바로가기

14891번: 톱니바퀴

 

문제 이해만 잘 하면 금방 풀 수 있다.

톱니바퀴 네 개가 일렬로 놓여져있고, 왼쪽 톱니바퀴의 2번째와 오른쪽 톱니바퀴의 6번째가 맞물려있는데, 회전하는 톱니바퀴 기준으로 맞물린 부분의 극이 서로 다르면 맞물린 다른 톱니바퀴도 도는 방식으로 작동한다.

 

따라서, 이를 DFS 백트래킹 방식으로 구현하였다.

rotate(int num, int dir)가 재귀적으로 호출되며, num은 톱니바퀴 번호, dir은 톱니바퀴가 회전하는 방향 정보를 담고있다.

회전하는 톱니바퀴 양 옆의 톱니바퀴가 회전가능한 조건(극이 달라야 함)을 가진다면 rotate 함수를 호출한다.

 

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string.h>
using namespace std;

int chain[4][8];
int check[3];
int visited[4];
int n;

void rotate_right(int num) {
	int tmp = chain[num][7];
	for (int i = 6; i >= 0; i--)
	{
		chain[num][i + 1] = chain[num][i];
	}
	chain[num][0] = tmp;
}

void rotate_left(int num)
{
	int tmp = chain[num][0];
	for (int i = 1; i <= 7; i++)
	{
		chain[num][i - 1] = chain[num][i];
	}
	chain[num][7] = tmp;
}

bool isIn(int num)
{
	if (num >= 0 && num < 4)
		return true;
	return false;

}
void rotate(int num, int dir)//dir == -1 : left 
{
	int converse_dir;
	visited[num] = 1;

	if (dir == -1) {
		rotate_left(num);
		converse_dir = 1;
	}
	else {
		rotate_right(num);
		converse_dir = -1;
	}
		

	if (!visited[num-1] && isIn(num - 1) && check[num - 1])
	{
		rotate(num - 1, converse_dir);
	}
		

	if (!visited[num+1] && isIn(num + 1) && check[num]) {
		rotate(num + 1, converse_dir);
	}
		

}

int main()
{
	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < 8; j++)
		{
			scanf("%1d", &chain[i][j]);
		}
	}

	cin >> n;
	
	for (int i = 0; i < n; i++)
	{
		int num, dir;
		cin >> num >> dir;
		for (int j = 1; j < 4; j++)
		{
			if (chain[j][6] != chain[j - 1][2])// 극이 다름
			{
				check[j - 1] = 1;
			}
		}
		rotate(num-1, dir);
		memset(visited, 0, sizeof(visited));
		memset(check, 0, sizeof(check));
	}

	int sum = 0;

	for (int i = 0; i < 4; i++)
	{
		if (chain[i][0] == 1)//S극
			sum += pow(2, i);
	}

	cout << sum << endl;

	return 0;
}