Boj 14891 c++ 톱니바퀴

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

 

문제

4개의 톱니바퀴가 순서대로 나열되어 있고, 각각의 톱니바퀴는 8개의 톱니를 갖고 있다. 각각의 톱니는 N극 또는 S극이다.

특정 톱니바퀴를 회전시켰을 때 해당 톱니바퀴와 이웃한 양옆의 톱니바퀴가 특정 규칙을 토대로 움직인다.

 

 

사진에서 서로 인접한 톱니가 서로 다른 극일 경우, 해당 톱니바퀴를 회전시킨 반대방향으로 한칸 회전한다.

서로 같은 극인 경우에는 회전하지 않는다.

 

ex) 사진에서 두번째 바퀴를 시계방향으로 회전시킬 경우 오른쪽으로 이웃한 바퀴는 인접한 톱니가 같은 S극이므로 움직이지 않고, 왼쪽으로 이웃한 바퀴는 S, N 극 으로 서로 다르기 때문에 왼쪽 바퀴가 반시계 방향으로 한칸 회전한다.

 

4개의 톱니바퀴에 대한 정보와 몇 번째 톱니바퀴를 어느 방향으로 회전시킬지에 대한 쿼리가 주어질 때, 최종적으로 12시 방향에 N극이 존재하는 것에 따라 점수를 부여하는 것이 문제이다.

 

 

입력조건

각각의 톱니에 대한 정보는 12방향 부터 시계방향으로 주어진다.

회전은 최대 100번까지 할 수 있다.

 

풀이

 

step 1. 원형 배열 만들기

톱니바퀴가 회전하는 것은 원형배열로 표현이 가능하다.

하지만 이 문제의 경우에는 톱니가 시계 방향 또는 반시계 방향으로 회전하기에 시작인덱스를 중간으로 설정해야 한다.

회전은 최대 100번이기에, 넉넉하게 150번째 인덱스에서 시작하겠다.

 

톱니바퀴에 대한 입력이 주어질 때, arr[i] 값을 arr[i + 8 * k] 와 arr[i - 8 * k] 까지 복사하여 원형 배열을 만든다.

 

 

step 2. 회전 정보 기억하기

원형 배열을 만들었기 때문에, 시작 인덱스를 조정해주는 것만으로도 회전 정보를 기억할 수 있다.

반시계 방향 회전은 시작 인덱스 +1, 시계 방향 회전은 시작 인덱스 -1을 해주면 된다.

각각의 톱니바퀴에 대해서 시작 인덱스를 기억하는 배열을 생성한다. 

step 3. 재귀함수 구현

하나의 톱니 바퀴를 회전할 때 마다 톱니 정보에 따라서 주변 바퀴들도 잇따라 회전하는 것은 재귀함수로 구현이 가능하다.

시작 인덱스는 12방향 톱니 기준이기 때문에, 오른쪽으로 인접한 톱니바퀴의 톱니를 검사할 때는 start_idx + 2와 start_idx - 2를 비교해주어야 하며, 왼쪽은 그 반대이다.

이렇게 인접한 톱니를 검사하여 서로 극이 다른 경우에는 그 바퀴에 대해서 또다시 회전함수를 호출하여 정보를 수정해준다.

각각의 회전에 대해서는 중복을 방지하기 위해서 방문처리를 해준다.

 

 

 

풀이 코드

 

#include <iostream>
using namespace std;

int arr[5][305], K;
int start_idx[4] ={150, 150, 150, 150};
int rotated[4] = {0,};
char c;

void Rotate(int N, int W) {
    rotated[N] = 1;
    if(N > 0) { // 좌측
        if(arr[N][start_idx[N] - 2] != arr[N-1][start_idx[N-1] + 2] && !rotated[N-1])
            Rotate(N-1, W * -1);
    }
    if(N < 3) { // 우측
        if(arr[N][start_idx[N] + 2] != arr[N+1][start_idx[N+1] - 2] && !rotated[N+1])
            Rotate(N+1, W * -1);
    }
    if(W == 1)
        start_idx[N] -= 1; // 시계 방향
    else
        start_idx[N] += 1; // 반시계 방향
}


int main() {

   for(int i = 0; i < 4; i++) {
        for(int j = 150; j < 158; j++) {
            cin >> c;
            arr[i][j] = c - '0';
            for(int k = 1; k <= 19; k++) {
                if(j + k * 8 <= 300)
                    arr[i][j + k * 8] = arr[i][j];
                if(j - k * 8 >= 0)
                    arr[i][j - k * 8] = arr[i][j];
            }
        }
    }

    cin >> K;

    while(K--) {
        int N, W; // 순서, 방향
        cin >> N >> W;
        N--;
        for(int i = 0; i < 4; i++)
            rotated[i] = 0;
        Rotate(N, W);
    }
    int ans = 0, score = 1;

    for(int i = 0; i < 4; i++) {
        if(arr[i][start_idx[i]])
            ans += score;
        score <<= 1;
    }
    cout << ans;
}