BOJ 14891 : 톱니바퀴 (삼성 SW TEST A형)

삼성 A형 전체 링크

 

www.acmicpc.net/workbook/view/1152 (A형 문제집)

 

www.acmicpc.net/problem/14891

 

이후 설명 및 입/출력은 링크 참고

 

시뮬레이션 문제는 시키는대로 구현하면 된다.

이 문제는 연속으로 회전이 발생하므로, DFS로 연속 회전 시켜보자.

 

먼저 rotate를 구현해보자.

톱니의 번호와 방향을 입력받으면 회전하는 함수는 아래와 같이 구현할 수 있다.

톱니바퀴 4개와 12시 방향 = 1 부터  8까지(순서대로 시계방향)의 톱니를 넣을 수 있는 2차원 배열을 선언하자.

int wheel[5][10]; /* wheel[번호 1~4][각 톱니 1~8] */

void rotate(int number, int dir)
{
	int temp;

	if (dir == -1) /* 반시계 방향 */
	{
		temp = wheel[number][1]; 
		for (int i = 1; i <= 7; i++) /* 한 칸씩 이동 */
		{
			wheel[number][i] = wheel[number][i + 1];
		}
		wheel[number][8] = temp;
	}
	else /* 시계 방향 */
	{
		temp = wheel[number][8];
		for (int i = 8; i >= 2; i--)
		{
			wheel[number][i] = wheel[number][i - 1];
		}
		wheel[number][1] = temp;
	}

	return;
}

 

rotate가 구현되었으니, rotate할지 저장하는 배열 list를 선언하고 아래와 같이 구현하자.

 

1) list에 입력값 list[톱니 바퀴 번호] = 회전 방향을 저장한다.

2) DFS를 이용해 톱니 바퀴 번호를 기준으로 양 옆의 톱니가 회전해야 하는지 list에 기록하자.

3) DFS 종료 후, list에 저장된 대로 rotate하자.

4) list를 초기화 하자.

for (int i = 0; i < N; i++)
{
	list[number[i]] = direct[i];
	DFS(number[i], direct[i]);

	for (int k = 1; k <= 4; k++)
		if (list[k] != 0) rotate(k, list[k]);

	for (int k = 1; k <= 4; k++) list[k] = 0;
}

 

DFS는 아래와 같이 구현할 수 있다.

현재 톱니바퀴의 왼쪽과 오른쪽이 회전해야 하는지 체크한다.

다음 DFS에서는 회전하는 방향이 반대가 되므로 -1을 곱해서 넣어주면 된다.

void DFS(int number, int dir)
{
	/* number를 기준으로 왼쪽 바퀴가 움직여야 하는지 체크 */
	if (check(number - 1, number) == 1 && list[number - 1] == 0) 
	{
		list[number - 1] = dir * (-1);
		DFS(number - 1, dir * (-1));
	}

	/* number를 기준으로 오른쪽 바퀴가 움직여야 하는지 체크 */
	if (check(number + 1, number) == 1 && list[number + 1] == 0)	
	{
		list[number + 1] = dir * (-1);
		DFS(number + 1, dir * (-1));
	}

	return;
}

check 함수는 톱니바퀴 옆이 존재하는지, 존재한다면 극이 같은지 체크한다.

list는 DFS에 의해 다시 돌아오지 않도록 막는다.

이미 list에 방향이 기록되어있다면 다시 check할 필요가 없기 때문이다.

(톱니바퀴가 회전한다면 1칸만 움직이므로)

 

check 함수는 아래와 같이 구현한다.

int check(int compare, int number)
{
	/* 비교할 톱니와 현재 톱니가 범위를 벗어나면 false */
	if (compare < 1 || compare > 4) return 0;
	if (number < 1 || number > 4) return 0;

	/* 비교대상이 왼쪽 톱니인 경우, 현재 톱니의 7번과 비교 톱니의 3번을 check */
	if (compare < number && wheel[number][7] != wheel[compare][3]) return 1;
    
    /* 비교대상이 오른쪽 톱니인 경우, 현재 톱니의 3번과 비교 톱니의 7번을 check */
	if (compare > number && wheel[number][3] != wheel[compare][7]) return 1;

	return 0;
}

톱니바퀴의 index 정의에 의해 3번과 7번의 극이 같은지 비교하면 된다.

 

점수 계산은 각 바퀴의 1번 index에 대해 점수를 계산하면 된다. (최종 코드 참고)

#include <stdio.h>

#define MAX (100 + 20)

int wheel[5][10];
int list[6];
int number[MAX];
int direct[MAX];
int N;

void input()
{
	for (int number = 1; number <= 4; number++)
	{
		for (int index = 1; index <= 8; index++)
		{
			scanf("%1d", &wheel[number][index]);
		}
	}

	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d %d", &number[i], &direct[i]);

	return;
}

void rotate(int number, int dir)
{
	int temp;

	if (dir == -1)
	{
		temp = wheel[number][1];
		for (int index = 1; index <= 7; index++)
		{
			wheel[number][index] = wheel[number][index + 1];
		}
		wheel[number][8] = temp;
	}
	else
	{
		temp = wheel[number][8];
		for (int index = 8; index >= 2; index--)
		{
			wheel[number][index] = wheel[number][index - 1];
		}
		wheel[number][1] = temp;
	}

	return;
}

int check(int compare, int number)
{
	
	if (compare < 1 || compare > 4) return 0;
	if (number < 1 || number > 4) return 0;

	if (compare < number && wheel[number][7] != wheel[compare][3]) return 1;
	if (compare > number && wheel[number][3] != wheel[compare][7]) return 1;

	return 0;
}

void DFS(int number, int dir)
{
	/* number를 기준으로 왼쪽 바퀴가 움직여야 하는지 체크 */
	if (check(number - 1, number) == 1 && list[number - 1] == 0) 
	{
		list[number - 1] = dir * (-1);
		DFS(number - 1, dir * (-1));
	}

	/* number를 기준으로 오른쪽 바퀴가 움직여야 하는지 체크 */
	if (check(number + 1, number) == 1 && list[number + 1] == 0)	
	{
		list[number + 1] = dir * (-1);
		DFS(number + 1, dir * (-1));
	}

	return;
}

int calculate()
{
	int sum, mul;

	sum = 0;
	mul = 1;
	for (int i = 1; i <= 4; i++)
	{
		sum += mul * wheel[i][1];
		mul *= 2;
	}

	return sum;
}

int main(void)
{
	int ans;

	input();

	for (int i = 0; i < N; i++)
	{
		list[number[i]] = direct[i];
		DFS(number[i], direct[i]);

		for (int k = 1; k <= 4; k++)
			if (list[k] != 0) rotate(k, list[k]);

		for (int k = 1; k <= 4; k++) list[k] = 0;
	}

	ans = calculate();

	printf("%d\n", ans);

	return 0;
}