[알고리즘] 백준 14891 톱니바퀴 // 구현, 배열회전

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

* 내풀이

• 0-idx로 만들기
• solve함수가 최종본
• 시계, 반시계를 예시를 통해 해보면서 결정
• vv에 회전대상 {톱니번호, 방향}을 담는게 특징

• 실수한부분 : i를 회전할게아니고 vv[i].first를 회전해야함

#include<bits/stdc++.h>
using namespace std;  

vector<int> topni[4]; //topni[0] : {1,0,1,0,1,1,1,1}
vector<pair<int,int>> v; // 명령어들
vector<pair<int,int>> vv; // [{회전대상톱니 idx, 방향}, ... ]
int k;

void goleft(int cur, int dir) {
    int nxt=cur-1;
    if(nxt<0) {
        return;
    }
    if(topni[nxt][2]!=topni[cur][6]) {
        vv.push_back({nxt,dir*-1});
        goleft(nxt,dir*-1);
    }
}

void goright(int cur, int dir) {
    int nxt=cur+1;
    if(nxt>=4) {
        return;
    }
    if(topni[nxt][6]!=topni[cur][2]) {
        vv.push_back({nxt,dir*-1});
        goright(nxt,dir*-1);
    }
}

void solve(int idx, int dir) {
    vv.clear();

    vv.push_back({idx,dir}); // 나 자신은 회전
    goleft(idx, dir);
    goright(idx,dir);
    for(int i=0;i<vv.size();++i) {
        // cout<<"c: "<<vv[i].first<<" "<<vv[i].second<<"\n";
        // cout<<vv[i].first<<" th is rotating.. \n"; //i가 아니고 vv[i]에 대상이 담겨있음!!!
        if(vv[i].second == 1) { // 시계
            // rotate(topni[i].begin(), topni[i].begin()+1, topni[i].end());
            rotate(topni[vv[i].first].begin(), topni[vv[i].first].begin()+topni[i].size()-1, topni[vv[i].first].end());
        }
        else { //반시계
            rotate(topni[vv[i].first].begin(), topni[vv[i].first].begin()+1, topni[vv[i].first].end());
            // rotate(topni[i].begin(), topni[i].begin()+topni[i].size()-1, topni[i].end());
        }
    }
}

void print() {
    for(int i=0;i<4;++i) {
        for(int j=0;j<8;++j) {
            cout<<topni[i][j];
        }
        cout<<"\n";
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // 입력
    for(int i = 0; i < 4; i++) {
        string tmp;
        cin>>tmp;
        for(int j=0;j<tmp.size();++j) {
            topni[i].push_back(tmp[j]-'0');
        }
    }

    cin >> k; 
    for(int i = 0; i < k; i++){
        int a,b;
        cin>>a>>b;
        a--; // 0-idx로 만듬
        solve(a,b);
        // print();
    }

    int ret=0;
    for(int i=0;i<4;++i) {
        if(i==0 && topni[i][0]==1) {
            ret+=1;
        }
        if(i==1 && topni[i][0]==1) {
            ret+=2;
        }
        if(i==2 && topni[i][0]==1) {
            ret+=4;
        }
        if(i==3 && topni[i][0]==1) {
            ret+=8;
        }
    }

    // 결과 출력
    cout << ret << "\n";
    return 0;
}

* 큰돌풀이

• vv에 회전대상을 저장 안함
• 왼쪽, 오른쪽 최대 갈수있는곳을 찾아서
• 바로회전
• string을 배열처럼 사용

#include<bits/stdc++.h> 
using namespace std;   
typedef long long ll;   

// n: 톱니바퀴의 개수, k: 회전 횟수, a: 회전시킬 톱니바퀴 번호, b: 회전 방향, ret: 결과값
int n, k, a, b, ret; 
string s[1004];  // 각 톱니바퀴의 상태를 저장하는 배열

// pos: 톱니바퀴 위치, dir: 회전 방향(0:시계, 1:반시계)
void rot(int pos, int dir){ 
    // 시계 방향 회전: 마지막 요소를 첫 번째로
    // 반시계 방향 회전: 첫 번째 요소를 마지막으로
    if(!dir) rotate(s[pos].begin(), s[pos].begin()+ 1, s[pos].end()); 
    else rotate(s[pos].begin(), s[pos].begin() + s[pos].size() - 1, s[pos].end());  
}    

// 현재 위치에서 왼쪽으로 회전 가능한 톱니바퀴 찾기
int findL(int pos){
    for(int i = pos; i >= 1; i--){
        // 인접한 톱니바퀴의 맞물리는 부분이 같으면 더 이상 회전 불가
        if(s[i][6] == s[i - 1][2]){
            return i; 
        }
    }
    return 0; 
}

// 현재 위치에서 오른쪽으로 회전 가능한 톱니바퀴 찾기
int findR(int pos){
    for(int i = pos; i <= n - 2; i++){
        // 인접한 톱니바퀴의 맞물리는 부분이 같으면 더 이상 회전 불가
        if(s[i][2] == s[i + 1][6]){
            return i; 
        }
    }
    return n - 1; 
}

int main(){
    cin >> n;  // 톱니바퀴 개수 입력
    for(int i = 0; i < n; i++){
        cin >> s[i];  // 각 톱니바퀴의 상태 입력
    }
    cin >> k;  // 회전 횟수 입력

    // k번 회전 수행
    for(int i = 0; i < k; i++){
        cin >> a >> b; a--;  // 톱니바퀴 번호(0-based로 변환)
        b = (b == -1 ? 0 : 1);  // 회전 방향 변환(-1 -> 0(시계), 1 -> 1(반시계))

        // 왼쪽과 오른쪽으로 회전 가능한 범위 찾기
        int l = findL(a); 
        int r = findR(a);  

        // 왼쪽 방향으로 회전
        int cnt = 0; 
        for(int pos = a; pos >= l; pos--){
            rot(pos, cnt % 2 == 0 ? b : !b);  // 톱니바퀴 회전
            cnt++;
        } 

        // 오른쪽 방향으로 회전
        cnt = 1; 
        for(int pos = a + 1; pos <= r; pos++){
            rot(pos, cnt % 2 == 0 ? b : !b);  // 톱니바퀴 회전
            cnt++;
        }
    }

    // 12시 방향이 1인 톱니바퀴 개수 세기
    for(int i = 0; i < n; i++)if(s[i][0] == '1')ret++;
    cout << ret << "\n";

    return 0;
}

이 부분은 톱니바퀴의 연쇄 회전을 구현한 코드입니다. 자세히 설명해드리겠습니다.

for(int pos = a; pos >= l; pos--){  // 현재 톱니바퀴(a)에서 왼쪽으로 이동
    rot(pos, cnt % 2 == 0 ? b : !b);  // 회전 방향 결정
    cnt++;
}

작동 원리를 시각화해서 설명하겠습니다:

코드 분석:

1. pos = a: 시작 톱니바퀴 위치
2. pos >= l: l은 findL()로 찾은 왼쪽 끝 위치
3. pos--: 왼쪽으로 한 칸씩 이동
4. cnt % 2 == 0 ? b : !b:
   • cnt가 짝수일 때: 원래 방향(b)
   • cnt가 홀수일 때: 반대 방향(!b)

예시:

초기 상태: [1][2][3][4] (톱니바퀴 번호)
시작 위치(a) = 2, 회전 방향(b) = 시계방향일 때

cnt = 0: 2번 톱니바퀴 시계방향 회전
cnt = 1: 1번 톱니바퀴 반시계방향 회전

이렇게 하는 이유:

• 맞물린 톱니바퀴는 서로 반대 방향으로 회전해야 함
• cnt를 이용해 홀수/짝수로 나누어 자동으로 방향 전환
• 연쇄적인 회전을 구현할 수 있음

이 코드는 기계적인 톱니바퀴의 실제 동작을 정확하게 시뮬레이션하고 있습니다.