BOJ - 14891 ) 톱니바퀴

 

---

 

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

14891번: 톱니바퀴

 

---

자성을가진 톱니바퀴가 도는데 인접한 극이 다를경우 그 톱니바퀴도 반대방향으로 돌게되는 시뮬레이션 문제이다.

 

문제의 알고리즘은

 

1 ) 명령으로 주어진 INDEX 번째의 톱니바퀴와 인접한 배열의 극성이 다른지 확인한다

 

2 ) 다르다면 DFS로 그 톱니바퀴로 이동하여 또 체크해준다.

 

3 ) DFS가 끝나면 한 TIME에 바꾸어야하는 회전결과를 R 배열에 넣어준다.

( 0 : 회전하지 않음 , 1 : 시계방향 회전 , -1 : 반시계 방향 회전 )

 

4 ) R대로 돌려주고 R을 초기화하고 1번으로 되돌아간다.

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int map[][] = new int[4][8];
	static int r[] = new int[4];
	static boolean v[] = new boolean[4];
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		for(int tc = 1 ; tc<=t ; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int k = Integer.parseInt(st.nextToken());
			for(int index = 0 ; index< 4 ; index++) {
				st = new StringTokenizer(br.readLine());
				for(int x = 0 ; x < 8 ; x++) {
					map[index][x] = Integer.parseInt(st.nextToken());
				}
			}
			
			int rotate[][] = new int[k][2]; 
			for(int index = 0 ; index < k  ; index++) {
				st = new StringTokenizer(br.readLine());
				rotate[index][0] = Integer.parseInt(st.nextToken())-1;
				rotate[index][1] = Integer.parseInt(st.nextToken());
			}
			
			for(int index = 0 ; index < k ; index++) {
				// 2번과 6번
				for(int i = 0 ; i < 4 ; i++) {
					r[i]=0; v[i] = false;	
				}
				r[rotate[index][0]] = rotate[index][1];
				dfs(rotate[index][0] , rotate[index][1]);
				for(int i = 0 ; i < 4 ; i ++) {
					if(r[i]==0) continue;
					Rotate(i, r[i]);
				}
			}
			
			int answer =0;
			if(map[0][0] ==1) answer+=1;
			if(map[1][0] ==1) answer+=2;
			if(map[2][0] ==1) answer+=4;
			if(map[3][0] ==1) answer+=8;
			System.out.println("#"+tc+" "+answer);
		}
		
	}
	
	public static void dfs(int index, int dir) {
		if(v[index]) return;
		v[index] = true;
		if(index -1 >=0 && !v[index-1]) {
			if(map[index-1][2] != map[index][6]) {
				if(dir==1) {
					r[index-1] = -1;
					dfs(index-1,-1);
				}
				else {
					r[index-1] = 1;
					dfs(index-1,1);
				}
			}
		}
		if(index +1 < 4 && !v[index+1]) {
			if(map[index+1][6] != map[index][2]) {
				if(dir==1) {
					r[index+1] = -1;
					dfs(index+1, -1);
				}
				else {
					r[index+1] = 1;
					dfs(index+1 , 1);
				}
			}
		}
	}

	public static void Rotate(int index, int dir) {
		int temp =0;
		if(dir ==1) {
			temp = map[index][7];
			for(int i = 7 ; i >=1 ; i--) {
				map[index][i] = map[index][i-1];
			}
			map[index][0] = temp;
		}
		else if(dir == -1) {
			temp = map[index][0];
			for(int i = 1 ; i < 8 ; i++) {
				map[index][i-1]=map[index][i];
			}
			map[index][7]=temp;
		}
		else return;
	}
	
	
}

 

---