14891 : 톱니바퀴

formula

• Grid 밀기(Rotate)

void rotate(int target, int dir) {
    if (dir == CW) {
        int temp = gears[target][7]; // 빼놓고
        for (int i = 7; i > 0; i--) {
            gears[target][i] = gears[target][i - 1]; //grid 밀기
        }
        gears[target][0] = temp; // fill
    }
    else { //CCW
        int temp = gears[target][0]; // 빼놓고
        for (int i = 0; i < 7; i++) {
            gears[target][i] = gears[target][i + 1]; //grid 땡기기
        }
        gears[target][7] = temp; // fill
    }
}

별의 별 회전이 다 있지만 이건 그냥 하나 미는 테크닉

• 전파(Recursive)

// Recursive 전파
void check_left(int target, int dir) {
    if (target < 0) return;

    // 다른 극이라면 회전(앞서 돌려진 기어랑)
    if (gears[target][2] != gears[target + 1][6]) {
        d[target] = dir;
        // Recursive로 끝까지 전파(밀리는건 반대로만 밀림)
        check_left(target - 1, -dir);
    }
}

void check_right(int target, int dir) {
    if (target > 3) return;

    // 다른 극이면 회전
    if (gears[target][6] != gears[target - 1][2]) {
        d[target] = dir;
        check_right(target + 1, -dir);
    }
}

하나 회전하고 다 따질 수가 없어서 재귀로 전파시켜놓고
나중에 일괄처리해서 돌리면 정답을 도출할 수 있음

Implementation

#include <iostream>
#include <vector>

using namespace std;

#define CCW -1 //반시계
#define CW 1 //시계

//12시=0 / 3시=2 / 6시=4 / 9시 = 6
int gears[4][8]; // N극은 0 / S극은 1
int d[4]; // 돌 방향(0 = 안돔 / 1 = CW / -1 = CCW)

int K; //회전 횟수

void rotate(int target, int dir) {
    if (dir == CW) {
        int temp = gears[target][7]; // 빼놓고
        for (int i = 7; i > 0; i--) {
            gears[target][i] = gears[target][i - 1]; //grid 밀기
        }
        gears[target][0] = temp; // fill
    }
    else { //CCW
        int temp = gears[target][0]; // 빼놓고
        for (int i = 0; i < 7; i++) {
            gears[target][i] = gears[target][i + 1]; //grid 땡기기
        }
        gears[target][7] = temp; // fill
    }
}

// Recursive 전파
void check_left(int target, int dir) {
    if (target < 0) return;

    // 다른 극이라면 회전(앞서 돌려진 기어랑)
    if (gears[target][2] != gears[target + 1][6]) {
        d[target] = dir;
        // Recursive로 끝까지 전파(밀리는건 반대로만 밀림)
        check_left(target - 1, -dir);
    }
}

void check_right(int target, int dir) {
    if (target > 3) return;

    // 다른 극이면 회전
    if (gears[target][6] != gears[target - 1][2]) {
        d[target] = dir;
        check_right(target + 1, -dir);
    }
}

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

    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 8; j++) {
            char temp;
            cin >> temp;
            gears[i][j] = temp - '0';
        }
    }

    cin >> K; //회전 횟수

    while (K--) {
        int target, dir; //회전 기어, 방향
        cin >> target >> dir;
        target--; // 0-based index

        // Re-Init
        for (int i = 0; i < 4; i++) {
            d[i] = 0;
        }

        // target 방향
        d[target] = dir;

        // 전파
        check_left(target - 1, -dir);
        check_right(target + 1, -dir);

        // Batch Processing
        for (int i = 0; i < 4; i++) {
            if (d[i] != 0) {
                rotate(i, d[i]);
            }
        }
    }

    int res = 0;
    if (gears[0][0] == 1) res += 1;
    if (gears[1][0] == 1) res += 2;
    if (gears[2][0] == 1) res += 4;
    if (gears[3][0] == 1) res += 8;

    cout << res << endl;
    return 0;
}