[BaekJoon/백준] 14891번 톱니바퀴

 

이번 문제에서 생각해야 될 핵심은,

 

"비교∙판단은 회전하기 전에 모두 처리되는 거고, 회전하는 것은 모든 판단 이후에 하면 된다는 것."

 

회전하고 나서 비교를 하면 안되므로, 일단 재귀적으로 현재 상태에 대해 대한 회전 값을 모두 계산한 뒤에 나중에 회전해준다.

 

각 톱니바퀴는 벡터로 표현하여, 0 ~ 7 까지의 인덱스 안에 S N 값을 넣어주었고

톱니바퀴가 몇번째 이냐에 따라, 재귀를 어떻게 진행할지를 결정한다(ex. 1번 톱니바퀴는 앞으로만 검사, 뒤에는 톱니가 없음. 2번 톱니바퀴는 앞뒤로 검사.. )

 

또한, visit을 이용하여 톱니바퀴 영향 계산이 무한반복으로 일어나지 않게 체크 처리해준다.

 

톱니바퀴를 나타내는 데에는 deque를 사용했다. 앞 뒤로 push pop이 가능한 자료구조이다.

#include <iostream>
#include <deque>
#include <cmath>
#include <cstring>

using namespace std;

deque<int> t[4]; // 0 ~ 7 까지의 톱니 4개
bool visit[4]; // 각 톱니바퀴 재귀할 때 무한으로 돌지 않게 방문처리.

int tmp, K, k1, k2;

// t1의 2와 t2의 6이 맞물리며
// t2의 2와 t3의 6이 맞물리며
// t3의 2와 t4의 6이 맞물린다

// 판단은 돌리기 전에 다 하고, 돌리는건 마지막에 돌리는 거임.
void rotate_t(int t_num, int direction) {
    
    visit[t_num] = true; // 방문처리
    
    
    if(t_num > 0 && !visit[t_num - 1]) { // 1번보다 크면 뒤쪽 고려해줌. 뒤쪽이 아직 처리되지 않았다면.
        if(t[t_num][6] != t[t_num - 1][2])
            rotate_t(t_num - 1, direction * -1);
    }
    
    if(t_num < 3 && !visit[t_num + 1]) { // 4번보다 작으면 앞쪽 고려해줌. 앞쪽이 아직 처리되지 않았다면.
        if(t[t_num][2] != t[t_num + 1][6])
            rotate_t(t_num + 1, direction * -1);
    }

    
    
    // 현재 톱니 실제로 돌리는건, 위의 고려사항이랑 재귀가 다 끝나고.
    
    if(direction == 1) { // 시계방향
        
        // 현재 톱니를 시계방향으로 돌림.
        int back = t[t_num].back();
        
        t[t_num].pop_back();
        t[t_num].push_front(back);
        
    } else { // 반시계 방향
        
        // 현재 톱니를 시계반대방향으로 돌림.
        int front = t[t_num].front();
        
        t[t_num].pop_front();
        t[t_num].push_back(front);

        
    }
}

int score() {
    
    
    int sco = 0;
    
    for(int i = 0; i < 4; i++) {
        
        sco += t[i][0] * pow(2, i);
    }
    
    return sco;
}

int main() {
        
    char ss[9];
    
    for(int i = 0; i < 4; i++) {
        cin >> ss;
        
        for(int j = 0; j < 8; j++)
            t[i].push_back(ss[j] - 48);
    }
    
    
    cin >> K;
    
    
    for(int i = 0; i < K; i++) {
        
        memset(&visit, 0, sizeof(visit));
        
        cin >> k1 >> k2;
                
        rotate_t(k1 - 1, k2);  // 톱니바퀴 번호는 zero - base 인덱스 이니까 -1을 해줌.
        
    }
    
    cout << score() << "\n";
}

 

입력 예시를 제대로 파악하지 않고 코딩했다가, 완성 단계에서 낭패를 봤다.

숫자로 입력받게끔 처리했는데,, 문자열로 입력받는게 편한 방식이었다.

그래서 숫자로 받아서 따로 파싱과정을 거쳐서 사용했다.

 

 

 

 

이번 문제의 교훈 : 문제 제대로 파악하자..