백준 15662번 톱니바퀴(2)

문제 링크입니다: https://www.acmicpc.net/problem/15662

15662번: 톱니바퀴 (2)

최근에 비슷한 문제를 푼 적이 있어서 쉽게 풀 수 있었던 문제였습니다.

회전시킬 톱니바퀴를 회전시키지 않은 상태에서 동시에 회전시킬 톱니바퀴들을 모두 찾아야하기 때문에 큐를 써야하고 시계 방향과 반시계 방향으로 돌리는 것을 쉽게 구현하기 위해 덱을 이용했습니다.

 

	#include <iostream>
	#include <vector>
	#include <string>
	#include <algorithm>
	#include <queue>
	#include <deque>
	using namespace std;
	const int MAX = 1000;
	//톱니바퀴
	deque<int> dq[MAX];
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	for (int t = 0; t < T; t++)
	{
	string s;
	cin >> s;
	for (int i = 0; i < s.length(); i++)
	dq[t].push_back(s[i] - '0');
	}
	int K;
	cin >> K;
	for (int k = 0; k < K; k++)
	{
	int num, dir;
	cin >> num >> dir;
	num -= 1;
	vector<pair<int, int>> v;
	v.push_back({ num, dir });
	//횐전시킬 톱니바퀴 찾음
	queue<pair<int, int>> q;
	q.push({ num, dir });
	bool visited[MAX] = { false, };
	visited[num] = true;
	while (!q.empty())
	{
	int cur = q.front().first;
	int d = q.front().second;
	q.pop();
	//왼쪽
	if(cur != 0)
	if (dq[cur][6] != dq[cur - 1][2] && !visited[cur -1])
	{
	visited[cur - 1] = true;
	q.push({ cur - 1, d * -1 });
	v.push_back({ cur - 1, d * -1 });
	}
	//오른쪽
	if(cur != T - 1)
	if (dq[cur][2] != dq[cur + 1][6] && !visited[cur + 1])
	{
	visited[cur + 1] = true;
	q.push({ cur + 1, d * -1 });
	v.push_back({ cur + 1, d * -1 });
	}
	}
	for (int i = 0; i < v.size(); i++)
	{
	int cur = v[i].first;
	int d = v[i].second;
	if (d == 1)
	{
	int temp = dq[cur].back();
	dq[cur].pop_back();
	dq[cur].push_front(temp);
	}
	else
	{
	int temp = dq[cur].front();
	dq[cur].pop_front();
	dq[cur].push_back(temp);
	}
	}
	}
	int result = 0;
	for (int t = 0; t < T; t++)
	if (dq[t][0] == 1)
	result++;
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~