[BOJ] 14891번 : 톱니바퀴

1. problem : 

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

 

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
string board[4];
int K; // Test case의 수 

deque<char> dq1;
deque<char> dq2;
deque<char> dq3;
deque<char> dq4;

void rotate(int w,deque<char>& dq) {
	if (w == 1) {
		dq.push_front(dq.back());
		dq.pop_back();
	}
	if (w == -1) {
		dq.push_back(dq.front());
		dq.pop_front();
	}
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 4; i++) cin >> board[i]; 
	cin >> K; 
	while (K--) {
		int numth,clock_way; 
		cin >> numth >> clock_way; 
		numth--;

		int isvis[4] = {};
		int clock_arr[4] = {};
		clock_arr[numth] = clock_way; // 첫번째 인덱스와 방향 기록  
		isvis[numth] = 1;
		queue<int> Q; 
		Q.push(numth); 
		while (!Q.empty()) {
			int cur = Q.front(); Q.pop(); 
			if (clock_arr[cur] == 0) continue;
			if (cur >= 1 && !isvis[cur - 1]) {
				if (board[cur][6] != board[cur - 1][2]) {
					clock_arr[cur - 1] = -clock_arr[cur];
					Q.push(cur - 1);
				}
				isvis[cur - 1] = 1;
			}
			if (cur + 1 < 4 && !isvis[cur + 1]) {
				if (board[cur][2] != board[cur + 1][6]) {
					clock_arr[cur + 1] = -clock_arr[cur]; 
					Q.push(cur + 1);
				}
				isvis[cur + 1] = 1;
			}
		}
		dq1.clear();
		dq2.clear();
		dq3.clear();
		dq4.clear();
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 8; j++) {
				if (i == 0) dq1.push_back(board[i][j]);
				if (i == 1) dq2.push_back(board[i][j]);
				if (i == 2) dq3.push_back(board[i][j]);
				if (i == 3) dq4.push_back(board[i][j]);
			}
		}
		if (clock_arr[0] != 0) rotate(clock_arr[0], dq1);
		if (clock_arr[1] != 0) rotate(clock_arr[1], dq2);
		if (clock_arr[2] != 0) rotate(clock_arr[2], dq3);
		if (clock_arr[3] != 0) rotate(clock_arr[3], dq4);

		for (int j = 0; j < 8; j++) {
			board[0][j] = dq1[j];
			board[1][j] = dq2[j];
			board[2][j] = dq3[j];
			board[3][j] = dq4[j];
		}
	}
	int sum = 0; 
	for (int i = 0; i < 4; i++) {
		if (board[i][0] == '1') sum += (1 << i);
	}
	cout << sum << '\n';
}

deque를 따로 4개 선언을 하다 보니, 코드가 비효율적이다. 

 

3. solution 2  :

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

int K;  // Test case의 수
deque<char> gears[4];  // 4개의 톱니바퀴를 각각 deque로 관리

void rotate(int w, deque<char>& dq) {
    if (w == 1) {  // 시계 방향 회전
        dq.push_front(dq.back());
        dq.pop_back();
    } else if (w == -1) {  // 반시계 방향 회전
        dq.push_back(dq.front());
        dq.pop_front();
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    for (int i = 0; i < 4; i++) {
        string s;
        cin >> s;
        gears[i] = deque<char>(s.begin(), s.end());  // string을 deque로 변환
    }

    cin >> K;
    while (K--) {
        int numth, clock_way;
        cin >> numth >> clock_way;
        numth--;  // 0-indexing으로 맞추기

        int clock_arr[4] = {};  // 각 톱니바퀴의 회전 방향을 기록
        clock_arr[numth] = clock_way;

        // 각 톱니바퀴의 회전 여부와 방향을 결정하는 BFS
        queue<int> Q;
        Q.push(numth);
        while (!Q.empty()) {
            int cur = Q.front();
            Q.pop();

            // 왼쪽 톱니바퀴와의 비교
            if (cur > 0 && clock_arr[cur - 1] == 0) {
                if (gears[cur][6] != gears[cur - 1][2]) {
                    clock_arr[cur - 1] = -clock_arr[cur];  // 반대 방향으로 회전
                    Q.push(cur - 1);
                }
            }

            // 오른쪽 톱니바퀴와의 비교
            if (cur < 3 && clock_arr[cur + 1] == 0) {
                if (gears[cur][2] != gears[cur + 1][6]) {
                    clock_arr[cur + 1] = -clock_arr[cur];  // 반대 방향으로 회전
                    Q.push(cur + 1);
                }
            }
        }

        // 모든 톱니바퀴에 대해 결정된 방향으로 회전 수행
        for (int i = 0; i < 4; i++) {
            if (clock_arr[i] != 0) {
                rotate(clock_arr[i], gears[i]);
            }
        }
    }

    // 최종 결과 계산
    int sum = 0;
    for (int i = 0; i < 4; i++) {
        if (gears[i][0] == '1') sum += (1 << i);
    }
    cout << sum << '\n';
}

deque를 배열로 만든 케이스이다. chatgpt의 코드다. 

 

4. solution 3 :

// Authored by : jihwan0123
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/dfcfa653b8494b3082959f248edfb200
#include <bits/stdc++.h>
using namespace std;

string board[4];

// x : 번호, dir : 방향, 1번의 회전을 처리하는 함수
void go(int x, int dir) {
  int dirs[4] = {};
  dirs[x] = dir;
  // 왼쪽으로 회전을 전파
  int idx = x;
  while (idx > 0 && board[idx][6] != board[idx-1][2]){
    dirs[idx-1] = -dirs[idx];
    idx--;
  }
  
  // 오른쪽으로 회전을 전파
  idx = x;
  while (idx < 3 && board[idx][2] != board[idx+1][6]){
    dirs[idx+1] = -dirs[idx];
    idx++;
  }

  for(int i = 0; i < 4; i++) {
    if(dirs[i] == -1)
      rotate(board[i].begin(), board[i].begin()+1, board[i].end());    
    else if(dirs[i] == 1)
      rotate(board[i].begin(), board[i].begin()+7, board[i].end());
  }
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  for (int i = 0; i < 4; i++) cin >> board[i];
  int k;
  cin >> k;
  while (k--) {
    int x, dir;
    cin >> x >> dir;
    go(x - 1, dir);
  }
  int ans = 0;
  for (int i = 0; i < 4; i++)
    if (board[i][0] == '1') ans += (1 << i);
  cout << ans;
}

/*
STL에 rotate 함수가 있어서 회전을 다소 편하게 처리할 수 있다.
*/

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/14891.cpp

basic-algo-lecture/0x0D/solutions/14891.cpp at master · encrypted-def/basic-algo-lecture

stl에 있는 rotate 함수가 쓰였다. 또한 , go라는 함수가 톱니바퀴의 값을 바꾸는 로직이 신기하다.