백준 14891 톱니바퀴 (C++)

안유태·2022년 9월 22일
0

알고리즘

목록 보기
43/239

14891번: 톱니바퀴

한 톱니바퀴가 회전하게 되면 인접한 톱니바퀴부터 회전할지 안 할지 결정해야 하므로 큐를 사용하여 나타내었다. 회전 조건 수 만큼 반복문을 돌면서 회전을 해주게 되는데 rotation이 회전을 해주는 함수이다. 함수를 보면 조건에 따라 큐에 추가해주는데 이때 인접한 톱니바퀴가 회전을 한다면 방향은 현재 톱니바퀴의 반대 방향으로 무조건 회전하므로 -1을 곱해주어 추가하였다. 회전은 문자열 앞 뒤에 추가해주는 방식으로 해주었다.
간단한 구현 문제였다.



#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <cstring>

using namespace std;

string s[4];
bool check[4];
vector<pair<int, int>> v;
int dn[2] = { -1,1 };
int K, res = 0;

void rotation(int a, int b) {
    queue<pair<int, int>> q;

    q.push({ a, b });
    check[a] = true;

    while (!q.empty()) {
        int n = q.front().first;
        int dir = q.front().second;

        q.pop();

        for (int i = 0; i < 2; i++) {
            int nn = n + dn[i];

            if (nn < 0 || nn>3) continue;
            if (check[nn]) continue;

            if (i == 0) {
                if (s[n][6] == s[nn][2]) {
                    q.push({ nn, 0 });
                }
                else {
                    q.push({ nn,dir * -1 });
                }
            }
            else {
                if (s[n][2] == s[nn][6]) {
                    q.push({ nn,0 });
                }
                else {
                    q.push({ nn,dir * -1 });
                }
            }

            check[nn] = true;
        }

        if (dir == 1) {
            char tmp = s[n][s[n].size() - 1];
            s[n].pop_back();
            s[n] = tmp + s[n];
        }
        else if (dir == -1) {
            char tmp = s[n][0];
            s[n].erase(s[n].begin());
            s[n] = s[n] + tmp;
        }
    }
}

void solution() {
    for (int i = 0; i < K; i++) {
        memset(check, 0, sizeof(check));
        int n = v[i].first;
        int dir = v[i].second;

        rotation(n, dir);
    }

   
    for (int i = 0; i < 4; i++) {
        if (s[i][0] == '1') res += pow(2, i);
    }

    cout << res;
}

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

    for (int i = 0; i < 4; i++) {
        cin >> s[i];
    }

    cin >> K;

    for (int i = 0; i < K; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({ a - 1,b });
    }

    solution();

    return 0;
}
profile
공부하는 개발자

0개의 댓글