[BOJ 15662] 톱니바퀴(2)

#문제

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

#풀이

이 문제는 시뮬레이션으로 하여 풀었습니다.

기존 톱니바퀴 문제에서 조금 더 진화된 문제로 4개가 아닌 T개의 톱니를 다 보아야 합니다.

해당 조건으로 인해 기준이 되는 톱니바퀴를 돌릴 경우 양쪽으로 전부 혹은 몇개만 돌아갈 수 있습니다.

돌아갈 수 있는 톱니바퀴를 찾을때 BFS 혹은 DFS로 확인하면서 찾을 수 있다고 생각했지만...

기준 톱니의 왼쪽 오른쪽을 나누어 따로 확인하는 방식으로 하였습니다.
BFS나 DFS로도 풀어 봐야겠습니다 :) 

혹시 BFS 혹은 DFS로 푸신 분들은 코드 공유좀 부탁드리겠습니다!

돌아간 톱니를 찾은 뒤에는 톱니 바퀴를 방향에 맞게 돌려주는 것을 총 K번 반복 하면 끝입니다.

톱니바퀴 문제에 비해 엄청 어려운 정도는 아니므로 1을 풀으셨다면, 도전해볼만 합니다!

톱니바퀴 문제 URL : https://www.acmicpc.net/problem/14891 

#코드

#include <iostream>
 
using namespace std;
string gears[1001];
int checkGears[1001];
int T;
 
void checkingRotateGear(int NumOfGear, int dir){
    checkGears[NumOfGear] = dir;
    
    //왼쪽 확인
    int nowNum = NumOfGear;
    int nowDir = dir;
    while(nowNum > 1){
        if(gears[nowNum][6] != gears[nowNum-1][2]){
            checkGears[nowNum-1] = nowDir * (-1);
        }else{
            break;
        }
        nowNum -= 1;
        nowDir = checkGears[nowNum];
    }
    //오른쪽 확인
    nowNum = NumOfGear;
    nowDir = dir;
    while (nowNum < T) {
        if(gears[nowNum][2] != gears[nowNum+1][6]){
            checkGears[nowNum+1] = nowDir * (-1);
        }else{
            break;
        }
        nowNum += 1;
        nowDir = checkGears[nowNum];
    }
}
 
void rotateGears(){
    for(unsigned int i = 1; i <= T; i++){
        //시계방향 회전
        if(checkGears[i] == 1){
            char tempLast = gears[i][7];
            string tempstr;
            tempstr += tempLast;
            for(unsigned int j = 0; j < 7; j++){
                tempstr += gears[i][j];
            }
            gears[i] = tempstr;
        }
        //반시계방향 회전
        else if(checkGears[i] == -1){
            char tempFirst = gears[i][0];
            string tempstr;
            for(unsigned int j = 1; j <= 7; j++){
                tempstr += gears[i][j];
            }
            tempstr += tempFirst;
            gears[i] = tempstr;
        }
    }
}
 
void initCheckGear(){
    for(unsigned int i = 0; i <= T; i++){
        checkGears[i] = 0;
    }
}
 
int main(){
    cin >> T;
    
    for(unsigned int i = 1; i <= T; i++){
        cin >> gears[i];
    }
    
    int K;
    cin >> K;
    
    for(unsigned int i = 0; i < K; i++){
        int NumOfGear, dir;
        cin >> NumOfGear >> dir;
        initCheckGear();
        checkingRotateGear(NumOfGear, dir);
        rotateGears();
    }
    
    int ans = 0;
    for(unsigned int i = 1; i <= T; i++){
        if(gears[i][0] == '1'){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}