BOJ 14891 톱니바퀴

문제출처 : https://www.acmicpc.net/problem/14891

1. 문제요약

- 8개의 톱니를 가진 4개의 톱니바퀴

- 특정 하나의 톱니바퀴를 시계, 반시계 방향으로 회전

- 마주보고 있는 톱니의 극이 반대이면 옆 톱니바퀴도 같이 회전함

2. 접근방법

- 시뮬레이션

3. 시간복잡도

4. 회고

- 시뮬레이션이 제일 귀찮아

- 톱니 회전을 재귀로 구현했는데... 현재 톱니바퀴를 굴리기 전에 좌우 살펴서 돌릴 수 있으면 재귀

  재귀가 끝난 뒤 현재 톱니바퀴 회전

  재귀가 무한루프에 빠지지 않도록 톱니바퀴에 check를 넣어서 돌린적이 있는지 없는지 확인

  이런식으로 했는데

- for문으로 할 수 있는 방법도 있네

  돌리는 톱니바퀴가 결정되면 좌우에 있는 톱니바퀴는 어디로 돌릴지 방향에 대한 정보를 dir[4]에 각각 저장

  톱니바퀴 4개를 돌면서 저장된 방향대로 톱니바퀴를 회전

소스코드

#include<iostream>
using namespace std;

#define left -1
#define right 1

char drill[6][8]; // 0, 5 가상의 톱니바퀴
bool check[6];

// 12시 0, 3시 2, 9시 6
void spin(int drillNum, int dir){
	check[drillNum] = true;

	if (drillNum == 0 || drillNum == 5)
		return;

	// 왼쪽 톱니바퀴
	if (!check[drillNum - 1] && (drill[drillNum][6] - '0') ^ (drill[drillNum - 1][2] - '0')){
		spin(drillNum - 1, -dir);
	}
	// 오른쪽 톱니바퀴
	if (!check[drillNum + 1] && (drill[drillNum][2] - '0') ^ (drill[drillNum + 1][6] - '0')){
		spin(drillNum + 1, -dir);
	}

	char temp;
	if (dir == left){
		temp = drill[drillNum][0];
		for (int i = 0; i < 7; i++){
			drill[drillNum][i] = drill[drillNum][i + 1];
		}
		drill[drillNum][7] = temp;
	}
	else if (dir == right){
		temp = drill[drillNum][7];
		for (int i = 7; i > 0; i--){
			drill[drillNum][i] = drill[drillNum][i - 1];
		}
		drill[drillNum][0] = temp;
	}
}

int main(void){
	freopen("text.txt", "r", stdin);
	for (int i = 1; i < 5; i++){
		for (int j = 0; j < 8; j++){
			cin >> drill[i][j];
		}
	}

	int k, drillNum, dir;
	cin >> k;

	for (int i = 0; i < k; i++){
		cin >> drillNum >> dir;
		for (int j = 0; j < 6; j++)
			check[j] = false;
		spin(drillNum, dir);
	}

	int ans = 0;
	for (int i = 1; i <= 4; i++){
		if (drill[i][0] == '1'){
			ans += (1 << (i - 1));
		}
	}

	cout << ans << "\n";
}

소스코드 : for문

#include <stdio.h>

int t[6][9];

int main() {

	int i, j, n, num, dir[6], k, tmp,ans;

	for (i = 0; i < 4; i++) 
		for (j = 0; j < 8; j++)
			scanf("%1d", &t[i + 1][j]);
	scanf("%d", &n);

	while (n--) {
		for (i = 0; i < 6; i++) dir[i] = 0;
		scanf("%d",&num);
		scanf("%d",&dir[num]);
		
		for (k = num; k > 0; k--) {
			if (t[k - 1][2] != t[k][6] && dir[k] == 1) dir[k - 1] = -1;
			else if (t[k - 1][2] != t[k][6] && dir[k] == -1) { dir[k - 1] = 1;}
		}
		for (k = num; k < 5; k++) {
			if (t[k + 1][6] != t[k][2] && dir[k] == 1) dir[k + 1] = -1;
			else if (t[k + 1][6] != t[k][2] && dir[k] == -1) dir[k + 1] = 1;
		}
		for (i = 0; i < 6; i++) {
			if (dir[i] == -1) {
				tmp = t[i][0];
				for (j = 0; j < 8; j++) {
					t[i][j] = t[i][j + 1];
				}
				t[i][7] = tmp;
			}
			if (dir[i] == 1) {
				tmp = t[i][7];
				for (j = 8; j > 0; j--) {
					t[i][j] = t[i][j - 1];
				}
				t[i][0] = tmp;
			}
		}
	}

	ans = t[1][0] + t[2][0] * 2 + t[3][0] * 4 + t[4][0] * 8;
	printf("%d",ans);
	
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]