백준 14891번 톱니바퀴

 

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

14891번: 톱니바퀴

 

 

문제에서 제시한 조건을 정리하면 아래와 같다.

 

- 현재 톱니바퀴가 회전하지 않는다 -> 옆에 있는 톱니바퀴도 회전하지 않는다.

(이 경우엔 맞닿은 극의 값을 비교할 필요가 없다.)

 

- 현재 톱니바퀴가 회전한다 -> 옆에 있는 톱니바퀴는 현재 톱니바퀴와 맞닿은 극 값이 같으면 회전하지 않는다.

                                    -> 옆에 있는 톱니바퀴는 현재 톱니바퀴와 맞닿은 극 값이 다르면 반대방향으로 회전한다.

 

 

<접근순서>

입력으로 받은 첫번째 톱니바퀴의 회전 방향에 따라 나머지 톱니바퀴들이 어디로 회전하는지 결정된다.

 

1. 제일 먼저 해야할 것은 4개의 톱니바퀴가 각각 어디로 회전하는지 구해야 한다.

2. 4개의 톱니바퀴가 어디로 회전하는지 정해졌다면 각 톱니바퀴를 방향에 맞게 회전시킨다.

3. 위 과정을 k번 반복한다.

 

 

 

제일 머리 아팠던 부분은 입력 값에 따라 각 톱니바퀴가 어디로 회전하는지 구하는 것이다. 시작 톱니바퀴 위치가 1, 2, 3, 4인 경우 4가지를 나눠서 노가다로 짜려고 했는데 코드가 너무 지저분해지고 이렇게 푸는게 의미 없다고 생각하여 check라는 함수를 구현하여 재귀함수를 이용하였다.

check함수의 인자는 현재 톱니바퀴의 위치와 방향을 의미한다.

 

시작 톱니바퀴 위치와 방향에 따라 나머지 톱니바퀴가 어디로 회전할 것인지 계산하였다.

cur은 현재 톱니바퀴, prev는 현재 톱니바퀴를 기준으로 왼쪽, next는 현재 톱니바퀴를 기준으로 오른쪽을 의미한다.

 

먼저 시작 톱니바퀴의 위치가 0~3 범위에 들어오는지 확인하였다. 시작 톱니바퀴는 어차피 해당 범위안에 들어오지만 나중에 재귀함수로 이용하기 때문에 이 조건을 먼저 따져야 한다.

 

함수의 dir 인자로 넘겨받은 값을 is_rotate[cur]에 저장하여 현재 톱니바퀴가 어디로 회전하는지 저장하였으며 톱니바퀴의 회전 방향이 정해지면 visited[]에 반드시 방문했다는 것을 체크해야 한다. 한번 회전 방향이 정해지면 바꿔서는 안되기 때문이다.

 

그 이후 prev, next를 구한 뒤 if문 안에서 prev와 next톱니바퀴가 어디로 회전할 것인지 결정한다.

어디로 회전할 것인지는 문제에서 정의한 조건에 따라 값을 정한다.

prev나 next의 회전 방향이 정해지면 그 옆의 톱니바퀴의 회전방향을 정해야 하므로 여기서 재귀로 다시 호출한다.

 

 

 

전체 코드

#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>

using namespace std;

int k;
int info[100][2];
int gear[4][8] = {0};
int is_rotate[4] = { 0 };
bool visited[4] = { 0 };
int ans = 0;



//회전 안 했으면 옆에 톱니바퀴도 회전 안함
//극이 같으면 회전x
//극이 다르면 반대방향으로 회전




void check(int cur, int dir) {	

	if (cur >= 0 && cur < 4) {
		is_rotate[cur] = dir;
		visited[cur] = 1;
		int prev = cur - 1;
		int next = cur + 1;

		
		if (prev >= 0 && visited[prev]==0) {//현재 톱니에서 왼쪽 톱니가 존재하면
			int cur_left = gear[cur][6];
			int prev_right = gear[prev][2];
			
			if (is_rotate[cur] == 0) //현재 톱니가 회전 안할경우
				is_rotate[prev] = 0;
			else if (prev_right == cur_left) { //극이 같은 경우
				is_rotate[prev] = 0;
			}
			else if (prev_right != cur_left) {//극이 다른 경우
				is_rotate[prev] = -dir;
			}
			check(prev, is_rotate[prev]);
		}

		if (next < 4 && visited[next]==0) {//현재 톱니의 오른쪽 톱니가 존재하면
			int cur_right = gear[cur][2];
			int next_left = gear[next][6];

			if (is_rotate[cur] == 0) //현재 톱니가 회전 안할경우
				is_rotate[next] = 0;
			else if (cur_right == next_left) { //극이 같은 경우
				is_rotate[next] = 0;
			}
			else if (cur_right != next_left) {//극이 다른 경우
				is_rotate[next] = -dir;
			}
			check(next, is_rotate[next]);
		}
		return;
	}
};


void cw_rotation(int arr[8]) { //시계방향 회전
	
	int temp[8];
	for (int i = 0; i < 8; i++) { // backup용 배열 생성 후 초기화
		temp[i] = arr[i];
	}

	for (int i = 0; i < 8; i++) {
		arr[i] = temp[((i + 7) % 8)];
	}
}

void ccw_rotation(int arr[8]) { //반시계방향 회전
	int temp[8];
	for (int i = 0; i < 8; i++) { // backup용 배열 생성 후 초기화
		temp[i] = arr[i];
	}
	
	for (int i = 0; i < 8; i++) {
		arr[i] = temp[((i + 1) % 8)];
	}
}




int main() {

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 8; j++) {
			scanf("%1d", &gear[i][j]);
		}
	}
	
	scanf("%d", &k);

	for (int i = 0; i < k; i++) {
		scanf("%d %d", &info[i][0], &info[i][1]);
	}




	for (int i = 0; i < k; i++) {

		// 각 톱니바퀴들이 어디로 회전하는지 체크
		check(info[i][0] - 1, info[i][1]); 


		// 방향에 맞게 각 톱니바퀴를 회전
		for (int j = 0; j < 4; j++) {
			if (is_rotate[j] == 0) continue;
			else if (is_rotate[j] == 1) cw_rotation(gear[j]);
			else if (is_rotate[j] == -1) ccw_rotation(gear[j]);
		}


		memset(visited, 0, sizeof(visited));
	}




	for (int i = 0; i < 4; i++) {
		if (gear[i][0] == 1) ans = ans + pow(2, i);
	}

	cout << ans;
	
	


	return 0;
}