백준[14891] - 톱니바퀴

문제

백준 14891 문제 보기

접근 방법

구현 문제다. 어떻게 톱니바퀴를 회전을 시킬지 결정하면 된다. 따라서 rotation 배열을 둬 어떤 방향으로 회전을 할지 저장한다. 그리고 톱니바퀴마다 회전 방향이 결정되면 톱니바퀴를 회전 시킨다.
톱니바퀴는 따로 회전을 시키지 않고 12시를 가르키는 인덱스를 바꿔가면서 풀면 실제로 배열을 움직이지 않아돼 더 빠른 시간에 풀 수 있다.

코드

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

using namespace std;

queue<pair<int, int>> q;
vector<string> wheels;
int chk[4];
int rotation[4];
int K;

void rotateWheel() {
    // 톱니바퀴는 0번째 인덱스가 12시 방향을 가리키고 시계방향으로 저장
    for(int i = 0; i < 4; i ++) {
        // 시계 방향 회전
        if(rotation[i] == 1) {
            char temp = wheels[i][7];
            wheels[i].pop_back();
            wheels[i].insert(wheels[i].begin(), temp);
        } 
        // 반시계 방향 회전
        else if(rotation[i] == -1) {
            char temp = wheels[i][0];
            wheels[i].erase(wheels[i].begin());
            wheels[i].insert(wheels[i].end(), temp);
        }
    }
}

int main() {
    for(int i = 0; i < 4; i ++) {
        string a;
        cin >> a;
        wheels.push_back(a);
    }

    cin >> K;
    int w, dir;
    while(K --) {
        memset(chk, 0, sizeof(chk));
        memset(rotation, 0, sizeof(rotation));
        cin >> w >> dir;
        w --;
        chk[w] = 1;
        rotation[w] = dir;
        q.push(make_pair(w, dir));
        while(!q.empty()) {
            int wh = q.front().first;
            int whDir = q.front().second;
            q.pop();

            if(wh >= 0 && wh < 4) {
                if(wh != 0 && chk[wh-1] == 0 && wheels[wh-1][2] - '0'!= wheels[wh][6] - '0') {
                    chk[wh-1] = 1;
                    rotation[wh-1] = -whDir;
                    q.push(make_pair(wh-1, -whDir));
                }
                if(wh != 3 && chk[wh+1] == 0 && wheels[wh][2] - '0' != wheels[wh+1][6] - '0') {
                    chk[wh+1] = 1;
                    rotation[wh+1] = -whDir;
                    q.push(make_pair(wh+1, -whDir));
                }
            }

        }
        // 톱니바퀴 회전
        rotateWheel();
    }

    int ans = 0;
    for(int i = 0; i < 4; i ++) {
        int cnt = wheels[i][0] - '0';
        if(cnt == 1) {
            if(i == 0) {
                ans += 1;
            } else if(i == 1) {
                ans += 2;
            } else if(i == 2) {
                ans += 4;
            } else {
                ans += 8;
            }
        }
    }
    cout << ans;
    return 0;
}