[BOJ 14891] 톱니바퀴(C++)

톱니바퀴(Gold 5)

문제

전체 문제 보기

14891번: 톱니바퀴

접근법

이번 문제는 문제에서 주어진 톱니바퀴의 로직을 구현하는 문제입니다. 톱니바퀴의 회전은 deque을 활용하여 구현할 수 있습니다. 시계방향으로 톱니가 회전하는 것은 deque의 가장 끝 원소를 deque의 가장 앞으로 옮기는 것과 같고, 반 시계방향으로 회전하는 것은 반대로 deque의 가장 앞의 원소를 deque의 가장 끝에 옮기는 것과 같기 때문입니다.

 

4개의 톱니바퀴가 필요하기 때문에 4개의 deque를 만든 후 회전시킬 임의의 n번째 톱니바퀴의 양쪽인 n-1 번째와 n+1 번째 톱니바퀴의 범위를 확인한 후 회전 여부를 판단할 수 있습니다. 이때 한번 회전한 톱니가 다시 회전되는 것을 막기 위해서 bool타입 배열 visited[4]를 사용하여 회전 여부를 기록할 수 있습니다.

전체 구현

#include <stdio.h>
#include <queue>
using namespace std;
deque<int> gear[4];
bool visited[4]{};
void rotate(int n, int dir)
{
    if (visited[n]) return;
    visited[n] = true;

    // 회전 하는 톱니의 왼쪽 톱니 회전여부
    if (n > 0)
        if(gear[n-1][2] + gear[n][6] == 1)
            rotate(n-1, dir * -1);
    // 회전 하는 톱니의 오른쪽 톱니 회전 여부
    if (n < 3)
        if (gear[n + 1][6] + gear[n][2] == 1)
            rotate(n + 1, dir * -1);

    if (dir == 1) // 시계방향
    {
        int back = gear[n].back();
        gear[n].pop_back();
        gear[n].push_front(back); 
    }
    else // 반시계방향
    {
        int front = gear[n].front();
        gear[n].pop_front();
        gear[n].push_back(front);
    }
}
int GetPoint()
{
    int sum{};
    int factor{ 1 };
    for (int i = 0; i < 4; ++i)
    {
        sum += gear[i][0] * factor;
        factor *= 2;
    }
    return sum;
}
void InitVisited()
{
    for (int i = 0; i < 4; ++i)
    {
        visited[i] = false;
    }
}
int main()
{
    for (int i = 0; i < 4; ++i)
    {
        char input[9];
        scanf("%s", input);
        for (int j = 0; j < 8; ++j)
        {
            gear[i].push_back(input[j] - '0');
        }
    }
    int K;
    scanf("%d", &K);
    while (K--)
    {
        int n, d;
        scanf("%d %d ", &n, &d);
        rotate(n - 1, d);
        InitVisited();
    }
    int answer = GetPoint();
    printf("%d\n", answer);

    return 0;
}