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

🔗문제 보러가기

14891번: 톱니바퀴

 

👨‍💻풀이 과정

 

톱니바퀴를 시계 혹은 반시계 방향으로 회전시키는 기능과 양 옆 톱니바퀴와 맞물린 이빨의 자석 극이 서로 다를 경우, 해당 톱니바퀴들 또한 재귀적으로 회전시켜주는 것이 핵심입니다. 이걸 어떻게 구현했는지 한 단계씩 차례대로 살펴보겠습니다.

 

우선 1번부터 4번 톱니바퀴의 각 이빨의 극 정보를 배열에다가 저장해줍니다.

#define GEARWHELL_COUNT 4

vector<string> gearWheels(GEARWHELL_COUNT + 1);
for (int i = 1; i <= GEARWHELL_COUNT; i++)
    cin >> gearWheels[i];

 

그 후, 톱니바퀴를 회전시키는 개수인 K 값을 입력 받아 루프를 돌면서, 회전시킬 톱니바퀴 번호와 방향을 정보를 받아줍니다. 이 정보를 토대로, 양 옆 톱니바퀴들을 재귀적으로 회전시켜 나갈 건데, 주의할 점이 있습니다. 회전을 진행한 톱니바퀴는 다시 회전시키면 안 됩니다.

 

이를 구별해주기 위해, 방문 처리를 위한 별도의 bool 배열을 생성하였습니다.

int K;
cin >> K;

while (K--)
{
    int gearWheelNumber, rotationDirection;
    cin >> gearWheelNumber >> rotationDirection;

    vector<bool> visited(GEARWHELL_COUNT + 1, false);
    RotateGearWheels(gearWheels, visited, gearWheelNumber, rotationDirection);
}

 

이 문제의 핵심 구현 함수인 RotateGearWheels()를 보겠습니다. 톱니바퀴의 각 이빨은 12시 방향에 있는 이빨을 기준으로 시계 방향으로 0, 1, 2, ..., 7 순서대로 인덱스를 매겨놓았습니다.

#define LEFT_INTERLOCKING_TOOTH 6
#define RIGHT_INTERLOCKING_TOOTH 2
#define GEARWHELL_COUNT 4
#define DIRECTION_COUNT 8

void RotateGearWheels(vector<string>& gearWheels, vector<bool>& visited, const int gearId, const int direction)
{
    visited[gearId] = true;
    int leftGearWheelId = gearId - 1, rightGearWheelId = gearId + 1;

    if (1 <= leftGearWheelId and !visited[leftGearWheelId])
    {
        if (gearWheels[leftGearWheelId][RIGHT_INTERLOCKING_TOOTH] != gearWheels[gearId][LEFT_INTERLOCKING_TOOTH])
            RotateGearWheels(gearWheels, visited, leftGearWheelId, -direction);
    }

    if (rightGearWheelId <= 4 and !visited[rightGearWheelId])
    {
        if (gearWheels[rightGearWheelId][LEFT_INTERLOCKING_TOOTH] != gearWheels[gearId][RIGHT_INTERLOCKING_TOOTH])
            RotateGearWheels(gearWheels, visited, rightGearWheelId, -direction);
    }
    
    // ...
}

 

크게 어려운 코드가 아니기에, 쉽게 이해하실 수 있을 거라 생각합니다. 1)현재 방문한 톱니바퀴를 방문 처리한 후, 2)양 옆 톱니바퀴의 번호를 구해, 3)회전시켜야 하는 상황일 경우에만 해당 톱니바퀴들을 회전시키는 로직입니다.

 

회전시켜야 하는 상황이란 왼쪽 톱니바퀴의 2번 이빨과 내 톱니바퀴의 6번 이빨의 극이 다를 경우, 오른쪽 톱니바퀴의 6번 이빨과 내 톱니바퀴의 2번 이빨의 극이 서로 다를 경우입니다. 이 때, 회전해야 하는 옆 톱니바퀴는 현재 내 톱니바퀴가 회전해야 하는 방향의 반대 방향이므로, 음수(-) 부호를 붙여서 함수를 실행시켜주었습니다.

 

위 로직을 통해 더 이상 양 옆에 회전할 톱니바퀴가 없는 톱니바퀴까지 왔을 경우, 이제 회전을 시작해주면 됩니다.

#define LEFT_INTERLOCKING_TOOTH 6
#define RIGHT_INTERLOCKING_TOOTH 2
#define GEARWHELL_COUNT 4
#define DIRECTION_COUNT 8

void RotateGearWheels(vector<string>& gearWheels, vector<bool>& visited, const int gearId, const int direction)
{
    // ...
    
    int rotationCount = 0, toothId = 0;
    char previousMagneticPole = gearWheels[gearId][toothId];
    char temp;

    while (rotationCount < DIRECTION_COUNT)
    {
        int nextToothId = (toothId + DIRECTION_COUNT + direction) % DIRECTION_COUNT;
        temp = gearWheels[gearId][nextToothId];

        gearWheels[gearId][nextToothId] = previousMagneticPole;
        previousMagneticPole = temp;
        toothId = nextToothId;
        rotationCount++;
    }
}

 

 

K 번 회전을 다 했다면, 1번 ~ 4번 톱니바퀴의 0번(12시 방향)이 S극일 경우에만 점수를 매겨서 출력해주면 되겠습니다.

#define S '1'

int CalculatedPoint(const vector<string>& gearWheels)
{
    int totalPoint = 0;
    for (int i = 1; i <= 4; i++)
        if (gearWheels[i][0] == S)
            totalPoint += 1 << (i - 1);

    return totalPoint;
}

 

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
#include <string>

using namespace std;
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
#define S '1'
#define LEFT_INTERLOCKING_TOOTH 6
#define RIGHT_INTERLOCKING_TOOTH 2
#define GEARWHELL_COUNT 4
#define DIRECTION_COUNT 8

int CalculatedPoint(const vector<string>& gearWheels)
{
    int totalPoint = 0;
    for (int i = 1; i <= 4; i++)
        if (gearWheels[i][0] == S)
            totalPoint += 1 << (i - 1);

    return totalPoint;
}

void RotateGearWheels(vector<string>& gearWheels, vector<bool>& visited, const int gearId, const int direction)
{
    visited[gearId] = true;
    int leftGearWheelId = gearId - 1, rightGearWheelId = gearId + 1;

    if (1 <= leftGearWheelId and !visited[leftGearWheelId])
    {
        if (gearWheels[leftGearWheelId][RIGHT_INTERLOCKING_TOOTH] != gearWheels[gearId][LEFT_INTERLOCKING_TOOTH])
            RotateGearWheels(gearWheels, visited, leftGearWheelId, -direction);
    }

    if (rightGearWheelId <= 4 and !visited[rightGearWheelId])
    {
        if (gearWheels[rightGearWheelId][LEFT_INTERLOCKING_TOOTH] != gearWheels[gearId][RIGHT_INTERLOCKING_TOOTH])
            RotateGearWheels(gearWheels, visited, rightGearWheelId, -direction);
    }

    int rotationCount = 0, toothId = 0;
    char previousMagneticPole = gearWheels[gearId][toothId];
    char temp;

    while (rotationCount < DIRECTION_COUNT)
    {
        int nextToothId = (toothId + DIRECTION_COUNT + direction) % DIRECTION_COUNT;
        temp = gearWheels[gearId][nextToothId];

        gearWheels[gearId][nextToothId] = previousMagneticPole;
        previousMagneticPole = temp;
        toothId = nextToothId;
        rotationCount++;
    }
}

int main()
{
    FAST_IO

    vector<string> gearWheels(GEARWHELL_COUNT + 1);
    for (int i = 1; i <= GEARWHELL_COUNT; i++)
        cin >> gearWheels[i];

    int K;
    cin >> K;

    while (K--)
    {
        int gearWheelNumber, rotationDirection;
        cin >> gearWheelNumber >> rotationDirection;

        vector<bool> visited(GEARWHELL_COUNT + 1, false);
        RotateGearWheels(gearWheels, visited, gearWheelNumber, rotationDirection);
    }

    cout << CalculatedPoint(gearWheels);
    return 0;
}