백준 14891 (톱니바퀴)

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

14891번: 톱니바퀴

풀이 

해당 문제는 재귀를 사용하여 회전시킬 톱니바퀴의 위치와 -1 or + 1 위치에 해당하는 톱니바퀴의 마주보는 면을 비교하며 회전시킬지 말지 선택하여 풀면 되는 문제이다.

주의 사항

예를들어 하나의 톱니바퀴가 회전하고 인접한 위치의 다른 톱니바퀴가 회전해야 한다면 다른 위치의 톱니바퀴를 기준으로 또 다른 톱니바퀴가 회전하는 경우의 수 까지 구해야 한다.

즉 3 번이 회전하고 그에 따라 2번 톱니바퀴가 회전하고 그에 따라 1번 톱니바퀴 까지 회전하는 경우의 수가 존재할 수 있다.

따라서 재귀함수를 구현할 때 바로 해당 INDEX에 해당하는 톱니바퀴를 회전시키는게 아니라 먼저 인접한 톱니바퀴가 회전해야 하는가 ? 확인을 한 뒤 만약 회전해야 할 경우 재귀를 통해 회전시킬 톱니바퀴의 인접한 다른 톱니바퀴를 다시 비교 하는 과정을 계속 진행하며 모든 과정이 끝나고 더이상 회전시킬 톱니바퀴가 없을 때 재귀함수를 반환하며 반환시에 톱니바퀴를 회전시켜야한다. 

즉 재귀를 타고 들어갈 때에는 돌리지 않고 회전시켜야 하는 모든 톱니바퀴가 어떤건지 구해졋을 때 재귀된 함수를 반환하며 톱니바퀴를 돌린다.

#include <iostream>
#include <string>

using namespace std;
char clock[4][9];

// 각 톱니바퀴의 중첩되는 경우를 거르기 위해 회전시킬 톱니바퀴의 Index에 check 할 배열 
int used[4];
int cmdCnt;

struct Node{
	int idx;
	int dir;
};
Node cmdList[101];

void spin(int dir, int idx){
	// y축은 dir로 고정
	if (dir == 1){
		// 시계 우측 밀기
		char tmp = clock[idx][7];
		for (int x = 7; x >= 1; --x){
			clock[idx][x] = clock[idx][x - 1];
		}
		clock[idx][0] = tmp;

	}
	if (dir == -1){
		// 반시계 좌측 밀기
		char tmp = clock[idx][0];
		for (int x = 0; x < 7; ++x){
			clock[idx][x] = clock[idx][x + 1];
		}
		clock[idx][7] = tmp;
	}
}

void dfs(int idx, int dir){
	if (used[idx] == 0){
		used[idx] = 1;
		if (idx == 0){
			// +1 우측 탐색 후 본인 회전
			if (used[idx + 1] == 0){
				if (clock[idx + 1][6] != clock[idx][2]){
					if (dir == 1){
						dfs(idx + 1, -1);
					}
					else{
						dfs(idx + 1, +1);
					}
				}
			}
			spin(dir, idx);
		}
		else if (idx == 3){
			// -1 좌측 탐색 후 본인 회전
			if (used[idx - 1] == 0){
				if (clock[idx - 1][2] != clock[idx][6]){
					if (dir == 1){
						dfs(idx - 1, -1);
					}
					else{
						dfs(idx - 1, +1);
					}
				}
			}
			spin(dir, idx);
		}
		else{
			// -1 좌측 +1 우측 전부 탐색 후 본인 회전
			if (used[idx - 1] == 0){
				if (clock[idx - 1][2] != clock[idx][6]){
					if (dir == 1){
						dfs(idx - 1, -1);
					}
					else{
						dfs(idx - 1, 1);
					}
				}
			}
			if (used[idx + 1] == 0){
				if (clock[idx + 1][6] != clock[idx][2]){
					if (dir == 1){
						dfs(idx + 1, -1);
					}
					else{
						dfs(idx + 1, 1);
					}
				}
			}
			spin(dir, idx);
		}
	}
}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	for (int i = 0; i < 4; ++i){
		for (int j = 0; j < 8; ++j){
			cin >> clock[i][j];
		}
	}
	cin >> cmdCnt;

	for (int i = 0; i < cmdCnt; ++i){
		cin >> cmdList[i].idx >> cmdList[i].dir;
	}

	for (int i = 0; i < cmdCnt; ++i){
		for (int j = 0; j < 4; ++j){
			used[j] = 0;
		}

		dfs(cmdList[i].idx -1, cmdList[i].dir);
	}
	int num = 0;
	if (clock[0][0] == '1') num += 1;
	if (clock[1][0] == '1') num += 2;
	if (clock[2][0] == '1') num += 4;
	if (clock[3][0] == '1') num += 8;

	printf("%d", num);



}