[백준 14891] 톱니바퀴

분류 

구현, 백트래킹

요구사항

제일 마지막 입력에서의 톱니 바퀴 구하기

풀이

문제의 흐름은

입력 -> 톱니 돌리기 -> 양 방향 확인하기 -> 정답 출력

입력

deque를 사용해서 시계 방향, 반시계 방향으로 돌릴 수 있도록 한다

톱니 돌리기

deque를 원형 큐로 생각해사 2번재, 6번째 위치를 좌, 우로 설정하여 양 옆과 비교한다

양 방향 확인하기

현재 톱니 바퀴 옆이 존재하는지와 다른 극성인지 확인한다

정답 출력

각 deque의 0번째 위치 값 확인

 

#include <string>
#include <vector>
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <deque>

using namespace std;
/*
10101111
01111101
11001110
00000010
2
3 -1
1 1
*/
int n;
deque<int> q[5];
int visit[5];
//dir 
void rotate(int num, int dir){
	if(dir==1){
		int temp=q[num].back();
		q[num].pop_back();
		q[num].push_front(temp);
	}
	else if(dir==-1){
		int temp=q[num].front();
		q[num].pop_front();
		q[num].push_back(temp);
	}
}
void solve(int num, int dir){
	visit[num]=1;
	int nowleft = q[num][6];
	int nowright = q[num][2];
	rotate(num,dir);
	if( num -1 >=0 && visit[num-1] == 0 ){
		int leftright = q[num-1][2];
		if(leftright != nowleft){
			solve(num-1,-dir);
		}
	}

	if( num +1 <=3 && visit[num+1] == 0 ){
		int rightleft = q[num+1][6];
		if(rightleft != nowright){
			solve(num+1,-dir);
		}
	}

}
int main(){
	for(int i=0 ; i <4 ; i++){
		for(int j=0 ; j <8 ; j++){
			char x;
			scanf(" %c",&x);
			if(x=='1'){
				q[i].push_back(1);
			}
			else{
				q[i].push_back(0);
			}
		}
	}
	scanf("%d",&n);
	for(int i=0 ; i < n ; i++){
		memset(visit,0,sizeof(visit));
		int x,y;
		scanf("%d%d",&x,&y);
		solve(x-1,y);
	}
	int ans=0;
	int cnt=1;
	for(int i=0 ; i <4 ; i++){
		if(q[i][0] ==1){
			ans+=cnt;
		}
		cnt*=2;
	}
	cout<<ans<<endl;
}