백준 14891 톱니바퀴

문제

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

14891번: 톱니바퀴

 

 

톱니바퀴가 동시에 돌아가는걸 코드로 구현만 하면 되는 문제였으나

"동시에 돌아가는 톱니바퀴의 상태"를 코드로 구현하는게 쉽지않았습니다.

 

톱니가 a b c d e   이 있고

c번 톱니를 회전 시계방향으로 회전 한다고 하면

1) 톱니 회전 방향을 왼쪽->오른쪽 / 오른쪽 -> 왼쪽 진행 방향으로 나뉘어서 상태를 판단한다.

 (1) 왼쪽 -> 오른쪽으로 진행 : c번 톱니바퀴의 2번 톱니 극성값 에 따라 d번 톱니바퀴의 상태가 영향을 받고, e번 톱니바퀴는 d번 톱니바퀴의 2번째 극성에 따라 영향을 받게된다.

 (2) 오른쪽 -> 왼쪽으로 진행 : c번 톱니바퀴의 6번 톱니 극성값에 따라 b번 톱니바퀴의 상태가 영향을 받고, a번 톱니바퀴는 b번 톱니바퀴의 6번째 극성에 따라 영향을 받게된다.

 

2) 톱니바퀴의 방향에 따라서 다음 톱니 바퀴 회전 여부를 판단한다.

 (1) 현재 코드에서는 톱니바퀴를 하나씩 확인하면서 동시에 톱니를 회전하고 있기때문에, 다음 톱니바퀴의 상태를 판단하기 위해서는

즉, d 톱니 바퀴가 돌아가고 나서 e 톱니 바퀴의 극성값과 d 톱니의 극성값을 비교한 다음에 e 톱니 바퀴의 회전 여부를 결정하게 된다. d 톱니바퀴가 이미 돌아간 상태에서 비교를 하면 안되기 때문에 d 톱니바퀴의 회전 직전 극성을 기록해두었다가  e 톱니 바퀴의의 극성과 비교하여 회전 여부를 결정해야한다.

 

3) 인접한 톱니가 회전가능한 상태라면 인접한 톱니의 회전 방향은 직전 톱니 회전 방향과 무조건 반대이므로 이 부분도 기록해두었다가 인접 톱니 회전할때 이용하였다.

 

4) 영향받는 톱니들의 회전이 모두 끝났으면 c번 톱니 바퀴도 회전해준다.

 

5) 톱니바퀴 값을 담는 자료구조는 depue를 이용하였다. 배열을 이용하여 한칸씩 오른쪽으로 밀고, 왼쪽으로 밀어도 되지만

회전 방향에 따라 앞 / 뒤 모두 삽입 삭제가 되는게 효율적이라고 생각했기 때문이다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
int k, num, dir;
vector<deque<int>> v;

void rotate(int i, int dir) {
    if (dir == 1) { 
        v[i].push_back(v[i][0]);
        v[i].pop_front();
    }
    else {
        v[i].push_front(v[i][7]);
        v[i].pop_back();
    }
}

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

    for (int i = 0; i < 4; i++) {
        string s;
        cin >> s;
        deque<int> tempDq;
        for (int j = 0; j < 8; j++) {
            tempDq.push_back(s[j] - '0');
        }
        v.push_back(tempDq);
    }

    cin >> k;
    while (k--) {
        cin >> num >> dir;
        num--;

        // 톱니바퀴 회전 퍼져나가는 방향이 왼쪽->오른쪽으로
        int electrode1 = v[num][2];
        int tempDir1 = dir;
        for (int i = num; i < 3; i++) {
            //인접 톱니의 극이 같으면 나머지 톱니들도 움직이지 않음.
            if (electrode1 == v[i + 1][6])
                break;

            //rotate 를 실행하면 한바퀴 돌리고 난 후의 바퀴상태로 다음 if문을 비교하게된다.
            //돌리기 전 바퀴의 electrode1를 기억해놓고 그 다음 if문에서 회전되기전 상태의 값과 비교해야한다.
            electrode1 = v[i+1][2];
            rotate(i + 1, tempDir1);
            tempDir1 = -1 * tempDir1;
        }
        
        // 톱니바퀴 회전 퍼져나가는 방향이 오른쪽->왼쪽으로
        int electrode2 = v[num][6];
        int tempDir2 = dir;
        for (int i = num; i > 0; i--) {
            //인접 톱니의 극이 같으면 나머지 톱니들도 움직이지 않음.
            if (electrode2 == v[i - 1][2])
                break;
            
            //rotate 를 실행하면 한바퀴 돌리고 난 후의 바퀴상태로 다음 if문을 비교하게된다.
            //돌리기 전 바퀴의 electrode2를 기억해놓고 그 다음 if문에서 회전되기전 상태의 값과 비교해야한다.
            electrode2 = v[i-1][6];
            rotate(i - 1, tempDir2);

            //인접 톱니는 반대 방향으로 움직여야한다.
            tempDir2 = -1 * tempDir2;
        }

        rotate(num, - 1 * dir);
    }

    int answer = 0;
    for (int i = 0; i < 4; i++) {
        answer += (v[i][0] == 0 ? 0 : (1 << i));
    }

    cout << answer << "\n";
    return 0;
}