[Baekjoon] 14891번: 톱니바퀴

 

 

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

14891번: 톱니바퀴

 

---

 

문제 해결 과정

착안

문제에서 요구하는 출력 형식에서 힌트(?)를 얻었는데, 톱니바퀴의 각 8 개 톱니의 N극, S극 상태를 비트 형태로 저장하고 비트 연산(bitwise operation)을 활용하여 문제를 해결하고자 하였다. 비트 연산을 사용하고자 한 곳은 아래와 같다.

 

• 톱니바퀴 정보에 대한 입력 처리
• 톱니바퀴의 회전
• 이웃한 톱니바퀴가 서로 맞물려 있는지를 판정
• 문제에서 출력으로 요구하는 답안의 계산

 

입력된 번호의 톱니바퀴를 회전할 때, 맞물려 있는 톱니바퀴들을 동시에 모두 회전시키기 위해서는 회전하기 전, 톱니바퀴가 서로 맞물려 있는 상태를 먼저 판단하여 한꺼번에 회전시켜야한다는 점에 유의하여 문제를 해결하고자 하였다.

 

구현

문제에서 톱니바퀴 당 톱니의 수는 8 개이므로, char 형의 자료형만으로도 톱니 상태를 비트로 표현 가능하다. 이때 비트 연산 중 오른쪽 시프트 연산(>>)의 경우 최상위 비트를 채우는 규칙이 컴파일러마다 다를 수 있고, 문제 해결에 있어서도 번거로우므로 unsigned char 형을 사용해 톱니바퀴 당 톱니 정보들을 숫자 하나로 저장하였다.

 

톱니바퀴를 회전하는 방향에 따라 시프트 연산(<<, >>)을 활용하고 연산을 통해 자리가 밀려 지워지는 비트가 1인 경우, 지워진 방향의 반대쪽 끝 비트 자리에 1을 추가하도록 별도 처리하였다.

* 아래 코드에서 Rotate() 함수 참고.

 

이웃한 톱니바퀴가 서로 맞물려 있는지를 판단하기 위해서는 왼쪽 톱니바퀴의 3시 방향 톱니(이진법으로 $2^5=32$의 자리)와 오른쪽 톱니바퀴의 9시 방향 톱니(이진법으로 $2^1=2$의 자리)가 서로 반대 극인지를 판단하면 되므로 배타적 비트 논리합(bitwise exclusive OR(XOR), ^) 연산을 활용하여 맞물린 여부를 계산하였다.

* 아래 코드에서 bool 형 배열 connected[] 참고.

 

위 과정들에 필요한 특정 방향의 톱니 데이터(N극, S극 여부)를 톱니바퀴 값으로부터 추출할 때, 16진수와의 비트 논리곱(bitwise AND, &) 연산을 활용하면 간편하게 추출할 수 있다.

 

• 비트 1000 0000 = 16진수 0x80 (시프트 연산을 통한 톱니바퀴 회전에 사용).
• 비트 0000 0001 = 16진수 0x01 (시프트 연산을 통한 톱니바퀴 회전에 사용).
• 비트 0010 0000 = 16진수 0x20 (3시 방향 톱니, $2^5=32$의 자리).
• 비트 0000 0010 = 16진수 0x02 (9시 방향 톱니, $2^1=2$의 자리).

 

한편, 맞물린 톱니바퀴들을 함께 회전시키는 동작은 왼쪽/오른쪽 방향을 나누어 두 개의 반복문으로 구현하였다. 반복문은 각각의 방향으로 인접한 맞물린 톱니바퀴가 존재하지 않을 때까지 현재 톱니바퀴의 회전과 반대 방향으로 인접한 톱니바퀴를 회전시킨 다음, 현재 톱니바퀴 번호를 인접한 톱니바퀴 번호로 갱신하는 과정을 반복하도록 구현하였다.

* 아래 코드에서 RotateFrom() 함수 참고.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

unsigned char Gears[4];

void Rotate(int gear, int dir)
{
	if (dir == 1)
		Gears[gear] = (Gears[gear] >> 1) + (Gears[gear] & 0x01 ? 0x80 : 0);
	else
		Gears[gear] = (Gears[gear] << 1) + (Gears[gear] & 0x80 ? 0x01 : 0);
}

void RotateFrom(int gear, int dir)
{
	bool connected[3];
	for (int i = 0; i < 3; i++)
		connected[i] = (Gears[i] & 0x20 ? 1 : 0) ^ (Gears[i + 1] & 0x02 ? 1 : 0);

	Rotate(gear, dir);

	int left = gear - 1;
	int dl = dir;
	while (left >= 0 && connected[left])
		Rotate(left--, dl = -dl);

	int dr = dir;
	while (gear < 3 && connected[gear])
		Rotate(++gear, dr = -dr);
}

int main()
{
	for (unsigned char& gear : Gears)
	{
		char num[9];
		cin >> num;

		for (int j = 0; j < 8; j++)
			if (num[j] == '1')
				gear += 1 << (7 - j);
	}

	int K;
	cin >> K;
	while (K--)
	{
		int gear, dir;
		cin >> gear >> dir;
		RotateFrom(gear - 1, dir);
	}

	int score = 0;
	for (int i = 0; i < 4; i++)
		score += Gears[i] & 0x80 ? 1 << i : 0;

	cout << score << "\n";
	return 0;
}

 

실행 결과