[BAEKJOON] 14891번 톱니바퀴

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

14891번: 톱니바퀴

 

문제조건

1. 톱니바퀴 4개, S극(1), N극(0) 존재
2. 각 톱니바퀴가 맞닿아있는 부분이 극이 다르면 다른 방향으로 회전, 같으면 맞닿아있는 톱니바퀴는 회전X
3. 12시방향부터 시계방향순서대로 8개의 톱니에 S, N 주어짐
4. 돌리는 과정을 모두 수행한뒤, 최종적인 톱니바퀴 상태에서 4개의 12시방향에 있는 S들의 합

문제 파악하는데 30분 정도 걸린거같다.

역시나 문제는 복잡하고 풀이 방법은 쉽겠지,,,,? 는 오산이었다.

뭔가 조건이 되게 까다로웠다.

접근방법

 

처음에는 그냥 DFS를 돌릴려고 하니, 4개의 톱니바퀴중에서 왼쪽방향과 오른쪽방향을 체크할때, 왼쪽방향에서 먼저 방향대로 움직인 것을가지고 오른쪽 방향을 체크하게 되어서, 생각한것과 다른 결과가 나왔다.

그래서 왼쪽, 오른쪽 따로따로 DFS를 돌려줬다.

이렇게 할때, 주의해야할점은 톱니바퀴를 돌리고 난뒤에 맞닿아 있는 부분을 체크하는 것이 아니라, 돌리기전에 맞닿아있는 부분이 서로 다른지 먼저 체크해줘야한다. 나는 이걸 위해서 따로 벡터로 저장해주고 비교했다.

1. out of bounds 유의하자!
   1. 배열의 인덱스를 잘못 참조하게 되면 런타임 에러가 난다. DFS를 탐색할때는 잘못된 인덱스를 참조하지 않기 위해 조건을 잘 걸어 주자!
2. 비교할 대상을 미리 저장해주자!

위 유의 사항만 지키면 이번 문제는 문제에서 주는 조건만 그대로 구현해주면 되는 구현문제였다.

 

소스코드

#include <iostream>
#include <vector>
using namespace std;

//최종 톱니바퀴의 상태 (12시 방향이 S극일때 점수) -> gear[n][0]의 값?
// S : 1	N : 0
// 1 : 시계		-1 : 반시계
vector<int> gear[6], v;
int k;
int res;

//톱니바퀴 왼쪽			
void left(int num, int d) {
	//시계방향
	vector<int> tmp = gear[num];
	if (d == 1) {
		for (int i = 0; i < 8; i++) {
			int idx = (i + 7) % 8;
			gear[num][i] = tmp[idx];
		}
	}
	//반시계 방향
	else {
		for (int i = 0; i < 8; i++) {
			int idx = (i + 1) % 8;
			gear[num][i] = tmp[idx];
		}
	}	
	
	if (num == 1) return;

	if (tmp[6] != gear[num - 1][2]) {
		left(num - 1, -d);
	}	
}

//톱니바퀴 오른쪽	
void right(int num, int d) {
	//시계방향
	vector<int> tmp = gear[num];
	if (d == 1) {
		for (int i = 0; i < 8; i++) {
			int idx = (i + 7) % 8;
			gear[num][i] = tmp[idx];
		}
	}
	//반시계 방향
	else {
		for (int i = 0; i < 8; i++) {
			int idx = (i + 1) % 8;
			gear[num][i] = tmp[idx];
		}
	}	
	if (num == 4) return;

	//tmp[2]가 left에서 바꾸기 전 상태가 되야함.
	if (tmp[2] != gear[num + 1][6]) {
		right(num + 1, -d);
	}
	return;
}

int main(){
	for (int i = 1; i <= 4; i++) {
		for (int j = 0; j < 8; j++) {
			char num;
			cin >> num;
			gear[i].push_back(num - '0');
		}
	}
	cin >> k;
	//회전 횟수
	for (int i = 0; i < k; i++) {
		int num, d;
		cin >> num >> d;
		v = gear[num];
		left(num, d);
		if (num == 4) continue;
		if(v[2] != gear[num+1][6]) right(num + 1, -d);
	}
	for (int i = 1; i <= 4; i++) {
		int tem = 1;
		if (gear[i][0] == 1) {
			for (int j = 1; j < i; j++) tem = tem * 2;
			res += tem;
		}
		
	}
	cout << res;
}