[C] 백준 14891번 톱니바퀴

 

안녕하세요 (. ❛ ᴗ ❛.)

오늘은 삼성 SW 역량 테스트 기출문제 中 톱니바퀴 문제를 풀어보았습니다.

 

백준 14891번

www.acmicpc.net/problem/14891

14891번: 톱니바퀴

 

문제가 그림으로 이루어져 있어서 꽤 복잡하고 길게 느껴지지만,

막상 문제를 읽어보면 생각보다 간단한 문제임을 알 수 있습니다.

현재 4개의 톱니바퀴가 존재하고 있고, 각 톱니바퀴에는 8개의 톱니가 있습니다.

톱니바퀴는 일렬로 놓여있기 때문에 톱니바퀴끼리 맞닿는 부분이 존재하게 됩니다.

각 톱니바퀴의 톱니에는 N극과 S극이 존재하고, 톱니바퀴를 회전하게 되면 맞닿는 부분에 영향을 끼칠 수 있습니다.

.

이번 문제는 구현을 위주로 하는 문제이기 때문에 코드를 보며 설명하겠습니다.

코드는 다음과 같습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int gear[4][8];
int k, number, direction;
int isRotate[4];
int score;

// initializing isRotate array
void init() {
	for (int i = 0; i < 4; i++)
		isRotate[i] = 0;
}

// rotating the gear 
void clock(int index) {
	int temp[8];
	for (int i = 0; i < 8; i++)
		temp[i] = gear[index][i];
	for (int i = 1; i < 8; i++)
		gear[index][i] = temp[i - 1];
	gear[index][0] = temp[7];
	
}
void unclock(int index) {
	int temp[8];
	for (int i = 0; i < 8; i++)
		temp[i] = gear[index][i];
	for (int i = 0; i < 7; i++)
		gear[index][i] = temp[i+1];
	gear[index][7] = temp[0];
}
void rotate(int index, int direction) {
	if (direction == 1)
		clock(index);
	else if (direction == -1)
		unclock(index);
	else
		return;
}

// checking whether to rotate or not
void left_check(int index, int direction) {
	if (index <= 0)
		return;
	if (gear[index][6] != gear[index - 1][2]) { // left side
		isRotate[index - 1] = direction * (-1);
		left_check(index - 1, direction * (-1));
	}
}
void right_check(int index, int direction) {
	if (index >= 3)
		return;
	if (gear[index][2] != gear[index + 1][6]) { // right side
		isRotate[index + 1] = direction * (-1);
		right_check(index + 1, direction * (-1));
	}
}
void check(int index, int direction) {

	left_check(index, direction);
	right_check(index, direction);

	for (int i=0; i<4; i++)
		rotate(i, isRotate[i]);
}

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", &number, &direction);
		init();
		isRotate[number - 1] = direction;
		check(number - 1, direction);
	}

	int temp = 1;
	for (int i = 0; i < 4; i++) {
		if (gear[i][0] == 1)
			score += temp;
		temp *= 2;
	}

	printf("%d", score);

	return 0;
}

 

설명에 들어가기에 앞서 isRotate 배열의 역할에 대해 설명드리겠습니다.

isRotate 배열은 어떤 톱니바퀴를 회전해야 하는지 나타내기 위해 선언한 배열입니다.

isRotate 배열 값으로는 -1, 0, 1이 들어갈 수 있는데

-1일 때는 반시계 방향,

0일 때(default 값)는 회전 x,

1일 때는 시계 방향으로 회전해야 한다는 것을 의미합니다.

.

코드는 총 3가지 부분으로 이루어져 있습니다.

1. isRotate 배열 초기화 (init 함수)

isRotate 배열은 회전 방법에 따라 달라지기 때문에 회전 방법을 입력받을 때마다 초기화를 해주어야 합니다.

총 K번 초기화한다고 생각하시면 됩니다.

 

2. 어떤 톱니바퀴를 회전할지 체크 (left_check, right_check, check 함수)

톱니바퀴의 왼쪽과 오른쪽의 맞닿은 부분을 확인하여 회전할지 여부를 결정합니다. (isRotate 배열에 저장)

톱니바퀴의 12시 방향의 상태가 0번 index로 입력을 받았기 때문에

가장 왼쪽의 상태는 6번 index를,

가장 오른쪽의 상태는 2번 index를 의미합니다.

.

left_check 함수는 왼쪽 방향에 있는 톱니바퀴를 확인하고,

왼쪽 톱니바퀴를 회전할 수 있는 상황이라면 더 왼쪽에 있는 톱니바퀴까지 확인해야 합니다.

이 부분은 재귀 함수로 구현을 하였습니다.

왼쪽 톱니바퀴를 회전하는 조건은

gear[index][6](톱니바퀴의 가장 왼쪽 상태)와 gear[index-1][2](왼쪽 톱니바퀴의 가장 오른쪽 상태)가 다른 상태일 때입니다.

.

right_check 함수는 left_check 함수와 마찬가지로 오른쪽 방향에 있는 톱니바퀴를 확인합니다.

오른쪽 톱니바퀴를 회전할 수 있다면, 재귀 함수를 통해 더 오른쪽에 있는 톱니바퀴까지 체크합니다.

오른쪽 톱니바퀴를 회전할 수 있는 조건은

gear[index][2](톱니바퀴의 가장 오른쪽 상태)와 gear[index+1][6](오른쪽 톱니바퀴의 가장 왼쪽 상태)가 서로 다른 상황일 때입니다.

.

톱니바퀴의 체크는 left_check 중 index가 0보다 클 때(왼쪽 톱니바퀴가 존재할 때),

right_check 중 index가 3보다 작을 때(오른쪽 톱니바퀴가 존재할 때)까지 반복합니다.

 

3. 톱니바퀴 회전 (clock, unclock, rotate 함수)

2번 과정을 통해 isRotate 배열에 적절한 값이 저장되었기 때문에 해당 값을 바탕으로 회전을 수행하면 됩니다.

회전의 종류로는 시계 방향과 반시계 방향이 존재하는데,

시계 방향(isRotate 값이 1)일 때는 배열을 오른쪽으로 한 칸씩 옮겨주고, (clock 함수)

반시계 방향(isRotate 값이 -1)일 때는 배열을 왼쪽으로 한 칸씩 옮겨주면 됩니다. (unclock 함수)

.

이렇게 3단계를 거치게 되면 1번의 회전을 수행한 것이 되기 때문에

문제에서 주어진 K번만큼 위의 과정을 반복하면 됩니다!

(참고로 저는 gear 배열을 0번부터 입력받았기 때문에 check 함수의 인자를 전달할 때

number의 1을 빼고 넘겨주었습니다!)

.

여담으로 저는 처음에 문제를 제대로 읽지 않아서 예시 설명과 같이 톱니바퀴의 상태가 제일 왼쪽부터 주어지는 줄 알았답니다,,

12시 방향부터 시계방향으로 입력이 들어온다는 점.. 유의하세요.. ☆★