14891 톱니바퀴

14891 톱니바퀴

문제 : https://www.acmicpc.net/problem/14891 [출처 : 백준 홈페이지]

풀이 : 톱니바퀴는 depue를 이용했습니다.

시계 방향 - 맨 뒤 값을 빼서 맨 앞에 push

반시계 방향 - 맨 앞 값을 빼서 맨 뒤에 push

처음 이동하는 톱니를 queue 넣고 왼쪽, 오른쪽 톱니를 확인해주면서 맞닿은 극이 다를 경우 queue에 넣어줍니다.

 
xxxxxxxxxx
#include<iostream>
#include<deque>
#include<string>
#include<queue>
using namespace std;
​
typedef struct top 
{
    int no;
    int dir;
public:
    top() {}
    top(int no, int dir) : no(no), dir(dir) {}
};
​
​
deque<int> dq[4];
queue<top> q;
bool visit[4] = {false,};
void wheelState(int num, int dir)
{
    q.push(top(num-1,dir));
    visit[num-1] = true;
​
    while (!q.empty())
    {
        int start = q.front().no;
        int dir = q.front().dir;
        int f = dq[start][2];
        int b = dq[start][6];
        q.pop();
​
        if (dir == 1)
        {
            int tmp = dq[start].back();
            dq[start].pop_back();
            dq[start].push_front(tmp);
        }
        else if (dir == -1)
        {
            int tmp = dq[start].front();
            dq[start].pop_front();
            dq[start].push_back(tmp);
        }
​
        if (start - 1 >= 0 && !visit[start - 1] && b != dq[start - 1][2]) //왼쪽
        {
            visit[start - 1] = true;
            if (dir == 1)
                q.push(top(start - 1, -1));
            else
                q.push(top(start - 1, 1));
        }
​
        if (start + 1 < 4 && !visit[start + 1] && f != dq[start + 1][6]) //오른쪽
        {
            visit[start + 1] = true;
            if (dir == 1)
                q.push(top(start + 1, -1));
            else
                q.push(top(start + 1, 1));
        }
    }
}
int main(void)
{
    for (int i = 0; i < 4; i++)
    {
        string str;
        cin >> str;
        for (int j = 0; j < 8; j++)
        {
            dq[i].push_back(str[j]-'0');
        }
    }
​
    int K;
    cin >> K;
    for (int k = 0; k < K; k++)
    {
        int num, dir;
        cin >> num >> dir; // 톱니 위치, 방향 1 - 시계방향, -1 반시계방향
        wheelState(num, dir);
        for (int i = 0; i < 4; i++)
            visit[i] = false;
    }
    int two = 1;
    int sum = 0;
    for (int i = 0; i < 4; i++)
    {
        if (dq[i][0] == 1)
            sum += two;
        two *= 2;
    }
​
    cout << sum << endl;
    return 0;
}