백준(BOJ) 15562 톱니바퀴(2)

문제 : https://www.acmicpc.net/problem/15662

15662번: 톱니바퀴 (2)

풀이 :

 

한번 돌릴때의 일어나는 모든 상호작용은 큐로 처리한다. 즉 어떤 한 시계의 방향을 돌렸을때의 양옆의 톱니바퀴가 돌려질 수 있고 그로인해 또 양옆에 톱니바퀴가 돌려질 수 있기 때문이다.

 

처음 상태에 톱니들이 어떤 극으로 맞닿아 있는지 beforeRotate 에 넣어준다.

 

큐에 넣을 조건으로 그 톱니바퀴를 돌린 적이 없어야 하고 beforeRotate의 값이 달라야 넣을 수 있다.

 

코드 ( C++ )

 

	#include <iostream>
	#include <string>
	#include <queue>
	#include <cstring>
	using namespace std;
	string t[1000];
	int T;
	int visited[1000];
	int beforeRotate[1000][2];
	void Rotate(string& s)
	{
	int temp = s[7];
	for (int i = 7; i > 0; --i)
	{
	s[i] = s[i - 1];
	}
	s[0] = temp;
	}
	void reverseRotate(string& s)
	{
	int temp = s[0];
	for (int i = 0; i < 7; ++i)
	{
	s[i] = s[i + 1];
	}
	s[7] = temp;
	}
	int main()
	{
	cin >> T;
	for (int i = 0; i < T; ++i)
	{
	cin >> t[i];
	}
	int k;
	cin >> k;
	queue<pair<int, int>> q;
	for (int i = 0; i < k; ++i)
	{
	int n1, n2;
	cin >> n1 >> n2;
	q.push({ n1-1,n2 });
	memset(visited, 0, sizeof(visited));
	//beforeRotate 정의
	for (int i = 0; i < T; ++i)
	{
	//왼
	beforeRotate[i][0] = t[i][6];
	//오
	beforeRotate[i][1] = t[i][2];
	}
	while (!q.empty())
	{
	int number = q.front().first;
	int dir = q.front().second;
	visited[number] = true;
	q.pop();
	if (dir == -1) {
	//반시계회전
	reverseRotate(t[number]);
	if (number - 1 >= 0 && beforeRotate[number - 1][1] != beforeRotate[number][0] && !visited[number - 1]) {
	q.push({ number - 1 , -dir });
	}
	if (number + 1 < T && beforeRotate[number + 1][0] != beforeRotate[number][1] && !visited[number + 1]) {
	q.push({ number + 1 , -dir });
	}
	}
	else if (dir == 1) {
	//시계회전
	Rotate(t[number]);
	if (number - 1 >= 0 && beforeRotate[number - 1][1] != beforeRotate[number][0] && !visited[number - 1]) {
	q.push({ number - 1 , -dir });
	}
	if (number + 1 < T && beforeRotate[number + 1][0] != beforeRotate[number][1] && !visited[number + 1]) {
	q.push({ number + 1 , -dir });
	}
	}
	}
	}
	int cnt = 0;
	for (int i = 0; i < T; ++i)
	{
	if (t[i][0] == '1')
	cnt++;
	}
	cout << cnt << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub