BOJ 백준 15662 톱니바퀴(2) [JAVA]

문제 : https://www.acmicpc.net/problem/15662

 

 

[ 문제 요약 ]

• 총 8개의 톱니를 가지고 있는 톱니바퀴 T 개가 일렬로 놓여있습니다.
• 톱니바퀴의 톱니는 N, S 극 중 하나를 갖습니다. 톱니바퀴에는 가장 왼쪽부터 1번 .. N 번까지 번호가 매겨져 있습니다.
• 톱니바퀴를 총 K 번 회전시키려 합니다. 회전은 시계, 반시계 방향이 있습니다.
• 톱니바퀴를 회전 시킬 때, 회전시킬 톱니바퀴 번호와 회전 방향이 주어집니다.
• 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있습니다.
• A 톱니가 회전할 때 그와 맞닿은 B 톱니의 극이 다르다면 B는 A가 회전한 방향과 반대 방향으로 회전합니다. 극이 같다면 회전하지 않습니다.
• 톱니를 회전하기 전에 모든 톱니의 회전 방향을 먼저 정한 후 회전 로직을 돌려야 합니다.
• 출력은 회전이 끝난 후 12시 방향이 S 극인 톱니의 개수를 출력합니다.

 

[ 테스트 케이스 설명 ]

4 // 톱니바퀴 수(1<=1000)
10101111// 톱니바퀴의 상태로 12시 방향부터 시계방향 순서대로 주어집니다. 0은 N, 1은 S극 입니다.
01111101
11001110
00000010
2 // 회전 횟수(1<=1000)
3 -1 // 회전시킨 톱니바퀴 번호, 방향( 시계:1, 반시계:-1)
1 1
회전이 끝난 후 12시방향이 S극인 톱니의 개수를 출력 : 3

 

[ 알고리즘 분류 ]

• 구현
• 시뮬레이션

 

[ 문제 해설 ]

 

톱니바퀴를 회전하기 전에 모든 톱니의 회전 방향을 미리 정해 놓습니다. 그 후 방향에 맞게 회전만 하면 되는 간단한 구현 문제입니다.

 

톱니바퀴 방향을 정하기 위해 시작 톱니바퀴 번호부터 재귀적으로 왼쪽과 오른쪽을 탐색하며 방향을 저장하도록 구현했습니다.

 

코드는 2가지로 작성했습니다. 톱니바퀴를 회전할 때, 톱니 배열 자체를 회전하는 방법이 있고, 톱니 배열은 놔두고 톱니의 12시 방향 인덱스만 변경해서 연산을 줄이는 방법이 있습니다. 테스트 케이스가 작아 속도는 차이 나지 않는듯합니다.

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main{
	
	static final int LEFT = 6;
	static final int RIGHT = 2;
	static int T, K;
	static int wheel[][];// 현재 톱니의 모양
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		wheel = new int[T][8];
		
		for(int i=0; i<T; i++)
		{
			String str = br.readLine();
			for(int j=0; j<8; j++)
				wheel[i][j] = str.charAt(j) - '0';
		}
		
		K = Integer.parseInt(br.readLine());
		while(K-->0)
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			int idx = Integer.parseInt(st.nextToken()) - 1;
			int dir = Integer.parseInt(st.nextToken());
			
			checkLeft(idx, dir);
			checkRight(idx, dir);
			turn(idx, dir);
		}
		
		int cnt = 0;
		
		for(int i = 0; i < T; i++)
			if(wheel[i][0] == 1)
				++cnt;
		
		System.out.print(cnt);
	}
	static void checkRight(int idx, int dir) {
		int rightIdx = idx + 1;
		
		if(rightIdx == T)
			return;
		
		if(wheel[idx][RIGHT] != wheel[rightIdx][LEFT])
		{
			checkRight(rightIdx, -dir);
			turn(rightIdx, -dir);
		}
	}
	static void checkLeft(int idx, int dir) {
		if(idx == 0)
			return;
		
		int leftIdx = idx - 1;
		
		if(wheel[leftIdx][RIGHT] != wheel[idx][LEFT]) {
			checkLeft(leftIdx, -dir);
			turn(leftIdx, -dir);
		}
	}
	static void turn(int idx, int dir) {
		if(dir == 1)// 시계방향
			turnRight(wheel[idx]);
		else if(dir < 0)// 반시계 방향
			turnLeft(wheel[idx]);
	}
	static void turnRight(int[] arr) {
		int last = arr[7];
		for(int i=6; i>=0; i--)
			arr[i + 1] = arr[i];
		arr[0] = last;
	}
	static void turnLeft(int[] arr) {
		int first = arr[0];
		for(int i=0; i<7; i++)
			arr[i] = arr[i + 1];
		arr[7] = first;
	}
}

 

[ 정답 코드 2]

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

class Main{

	static int T, K;
	static int wheel[][];// 현재 톱니의 모양
	static int wheelTop[];// 각 톱니마다의 12시 방향의 인덱스
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		wheel = new int[T][8];
		wheelTop = new int[T];
		
		for(int i=0; i<T; i++)
		{
			String str = br.readLine();
			for(int j=0; j<8; j++)
				wheel[i][j] = str.charAt(j) - '0';
		}
		
		K = Integer.parseInt(br.readLine());
		
		while(K-->0)
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			int idx = Integer.parseInt(st.nextToken()) - 1;
			int dir = Integer.parseInt(st.nextToken());
			
			checkLeft(idx, dir);
			checkRight(idx, dir);
			turn(idx, dir);
		}
		
		int cnt = 0;
		
		for(int i = 0; i < T; i++)
			if(wheel[i][wheelTop[i]] == 1)
				++cnt;
		
		System.out.print(cnt);
	}
	static void checkRight(int idx, int dir) {
		int nextIdx = idx + 1;
		
		if(nextIdx == T)
			return;
		
		int right = (wheelTop[idx] + 2) % 8;
		int left = (wheelTop[nextIdx] - 2 + 8) % 8;
		
		if(wheel[idx][right] == wheel[nextIdx][left])
			return;
		
		checkRight(nextIdx, -dir);
		turn(nextIdx, -dir);
	}
	static void checkLeft(int idx, int dir) {
		if(idx == 0)
			return;
		
		int nextIdx = idx - 1;
		
		int right = (wheelTop[nextIdx] + 2) % 8;
		int left = (wheelTop[idx] - 2 + 8) % 8;
		
		if(wheel[nextIdx][right] == wheel[idx][left])
			return;
		
		checkLeft(nextIdx, -dir);
		turn(nextIdx, -dir);
	}
	static void turn(int idx, int dir) {
		if(dir == 1)// 시계방향
			wheelTop[idx] = (wheelTop[idx] - 1 + 8) % 8;
		else if(dir < 0)// 반시계 방향
			wheelTop[idx] = (wheelTop[idx] + 1) % 8;
	}
}

 

[ 테스트 케이스 ]

4
10101111
01111101
11001110
00000010
2
3 -1
1 1
답 : 3

4
11111111
11111111
11111111
11111111
3
1 1
2 1
3 1
답 : 4

4
10001011
10000011
01011011
00111101
5
1 1
2 1
3 1
4 1
1 -1
답 : 2

4
10010011
01010011
11100011
01010101
8
1 1
2 1
3 1
4 1
1 -1
2 -1
3 -1
4 -1
답 : 2

5
10010011
01010011
11100011
01010101
01010011
10
1 1
2 1
3 1
4 1
1 -1
2 -1
3 -1
4 -1
5 1
5 -1
답 : 5