14891. 톱니바퀴

https://www.acmicpc.net/problem/14891

14891번: 톱니바퀴

 

풀이

덱(deque)을 활용하여 톱니바퀴의 회전을 구현하면 크게 어렵지는 않다.

 

필자의 경우 톱니바퀴를 회전하는 함수를 하나 만들고, 톱니바퀴 하나가 회전하면 좌우 톱니바퀴를 회전하는 함수를 재귀 호출하도록 코드를 작성하였다. 이때, 톱니바퀴의 회전 여부를 확인했는지 저장하는 변수를 별도로 만들어 두도록 한다. 그렇지 않으면 재귀로 인해 이미 확인한 톱니바퀴를 다시 확인하게 되어 무한 루프가 발생할 수 있다.

 

소스코드

#include <iostream>
#include <deque>
using namespace std;

deque<char> gear[4];
bool checked[4];
int k, n, m;
int ans;

// 톱니바퀴를 회전하는 함수
void rotate(int num, int wise) {
    // 톱니바퀴가 회전하는지 여부를 확인하였음
    checked[num] = true;
    
    // 조건이 맞으면 좌측, 우측 톱니바퀴를 회전하는 함수 호출
    if(num - 1 >= 0 && !checked[num - 1] && gear[num - 1][2] != gear[num][6])
        rotate(num - 1, wise * -1);
    if(num + 1 < 4 && !checked[num + 1] && gear[num][2] != gear[num + 1][6])
        rotate(num + 1, wise * -1);
    
    if(wise == 1) {
        gear[num].push_front(gear[num].back());
        gear[num].pop_back();
    }
    else {
        gear[num].push_back(gear[num].front());
        gear[num].pop_front();
    }
    checked[num] = false;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string str;
    for(int i = 0; i < 4; i++) {
        cin >> str;
        for(char c : str) gear[i].push_back(c);
    }
    cin >> k;
    
    while(k--) {
        cin >> n >> m;
        rotate(n - 1, m);
    }
    
    // 최종 점수 계산
    for(int i = 0; i < 4; i++) {
        if(gear[i][0] == '1') ans += (1 << i);
    }
    cout << ans;
    return 0;
}

4개의 톱니바퀴 각각을 deque으로 구현하였다. 그리고 각 톱니바퀴 deque의 2, 6번 인덱스를 서로 비교하여 톱니바퀴가 회전하는지 여부를 확인할 수 있다.

 

소소한 코딩 팁으로, 회전하는 방향이 1, -1 두 가지로 정해져 있으므로 각 숫자에 -1을 곱하면 회전 방향을 간단하게 바꿀 수 있다. 최종 점수 역시 2의 (각 톱니바퀴 번호 - 1)제곱으로 정해져 있으므로, 이를 이용하면 간결하게 코드 작성이 가능하다.