백준 14891번 톱니바퀴 - C++(cpp) 풀이

---

 

1. 각 톱니바퀴를 그래프의 정점으로 보고, 인접해있으면서 맞닿는 톱니의 극이 반대인 톱니바퀴들은 간선으로 연결되어 있다고 생각한다.
2. 최초로 회전시키는 톱니바퀴에서 시작해 DFS로 회전의 전이를 구현한다.

 

1. 각 톱니바퀴를 그래프의 정점으로 보고, 인접해있으면서 맞닿는 톱니의 극이 반대인 톱니바퀴들은 간선으로 연결되어 있다고 생각한다.

 인접하면서 맞닿는 극이 반대인 톱니바퀴로만 전이가 일어날 수 있으므로, 그런 톱니바퀴들끼리만 간선으로 연결되어있다고 생각하자.

 

2. 최초로 회전시키는 톱니바퀴에서 시작해 DFS로 회전의 전이를 구현한다.

 회전 쿼리가 주어질 때마다 DFS로 회전의 전이를 시뮬레이션하면 된다. 전이는 회전하기 전의 상태를 기준으로 결정되기 때문에 rotate를 재귀 호출 이후에 실행해주어야 함을 유의한다.

 회전의 구현은 배열 값을 직접 하나씩 밀거나 당겨도 되지만, 시작점(12시 방향)을 저장해놓고 톱니에 접근할 때 시작점을 고려해서 접근해주면 조금 더 간단한 구현이 가능하다.

 

반응형

---

#include <iostream>

using namespace std;

const int N = 4, M = 8, NINE = 6, THREE = 2, CCW = -1, CW = 1;

int K;
int gear[N][M];
int start[N];    // 12시 방향의 인덱스

void rotate(int idx, int d) {
    if (d == CCW) {
        start[idx] = (start[idx] + 1) % M;
    } else {
        start[idx] = (start[idx] + M - 1) % M;
    }
}

// transfer(from, to, d): from번 톱니바퀴가 d방향으로 돌았을 때, to에게 전이시킨다.
void transfer(int from, int to, int d) {
    if (to < 0 || to >= N) return;
    
    if (from < to) {    // 좌 -> 우
        int l = gear[from][(THREE + start[from]) % M];
        int r = gear[to][(NINE + start[to]) % M];
            
        if (l != r) {
            transfer(to, to+1, -d); // 우측으로 전이
            rotate(to, -d);
        }
    } else {            // 우 -> 좌
        int l = gear[to][(THREE + start[to]) % M];
        int r = gear[from][(NINE + start[from]) % M];
        
        if (l != r) {
            transfer(to, to-1, -d); // 좌측으로 전이
            rotate(to, -d);
        }
    }
}

void simulate(int idx, int d) {
    transfer(idx, idx-1, d);
    transfer(idx, idx+1, d);
    rotate(idx, d);
}

int calc_score() {
    int ret = 0;
    
    for (int i=0; i<N; i++) {
        if (gear[i][start[i]]) {
            ret += (1 << i);
        }
    }
    
    return ret;
}

int main()
{
    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL); cout.tie(NULL);
    
    for (int i=0; i<N; i++) {
        for (int j=0; j<M; j++) {
            scanf("%1d", &gear[i][j]);   
        }
    }
    
    cin >> K;
    
    int idx, d;
    
    for (int i=0; i<K; i++) {
        cin >> idx >> d;
        simulate(idx-1, d);
    }
    
    cout << calc_score();

    return 0;
}