문제 바로가기

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

문제 소개 및 재정의

1. 4개의 톱니바퀴가 있다.
2. 톱니의 개수는 8개이다. (1번 톱니~8번 톱니)
3. 톱니에는 자성이 있다. N극과 S극
4. 톱니 8개의 자성 배치는 케이스마다 다르다.
5. 톱니바퀴(기어) 4개는 나란히 붙어있다.
6. 왼쪽 톱니바퀴의 3번 톱니와 오른쪽 톱니의 7번 톱니는 인접해있다.
7. 왼쪽 톱니바퀴의 3번 톱니와 오른쪽 톱니바퀴의 7번 톱니의 극성이 서로 반대일때, 하나가 회전하면 다른 하나는 반대 방향으로 회전한다.

문제 패턴

시뮬레이션으로 구현하는 방법이 일반적이다.

어떻게 풀까? - 시뮬레이션

포인트

톱니바퀴의 구현

먼저 톱니바퀴를 뭐로 구현할지 고민했다.

• 1*8 배열
  장점: 톱니바퀴와 회전의 구현이 간편하다.
  단점: 회전시 업데이트 비용이 톱니의 개수에 비례한다.
• 3*3 배열
  장점: 시각적으로 눈에 잘 들어온다. 논리적으로 직관적이다.
  단점: 회전시 인덱스를 바꿔주는 로직이 추가로 필요하다. 업데이트 비용이 톱니의 개수에 비례한다.
• Deque
  장점: 톱니바퀴와 회전의 구현이 간편하다. 회전시 업데이트 비용이 상수다.
  단점: 회전을 전파시킬때 3번 톱니와 7번 톱니의 값을 알아야 하는데 이것이 번거롭다.
  .
  고민결과 1*8로 결정했다.
  이유는 구현이 간편하고 비용은 문제를 푸는데 방해되지 않기 때문이다.

톱니바퀴의 회전구현

값들을 회전방향으로 한칸씩 밀어버리고 마지막 값만 스왑하는 방식으로 구현할수 있다.

배열을 깊은 복사해서 회전방향에 맞게 인덱스를 계산하고 원본의 인덱스에 값을 넣어주는 방식도 있다.
이 방식이 위의 방식보다는 메모리와 시간복잡도 손해가 발생하지만,
코드가 간결해지기에 이 방법을 선택했다.
메모리와 시간복잡도도 현재 문제의 입력크기를 능히 소화할수 있다.

여기서 조금만 최적화를 하고싶다면 .clone을 사용하지 말고.
Static으로 선언한 배열을 for문으로 복사해주면 메모리 사용량은 최적화할수 있을것이다.

시계방향(+1)으로 회전시 오버플로우를 구현해야한다.
0번(1번) => 1번
1번 => 2번
2번 => 3번
3번 => 4번
4번 => 5번
5번 => 6번
6번 => 7번
7번 => 0번
i번째 톱니는 (i+1)%8번째 톱니의 자리로 이동하게 된다.

• 다음 위치로 이동시키기 위해서 +1을 해주고.
• 오버플로우를 구현시키기 위해서 %8을 해준다.

반시계방향(-1)으로 회전시 언더플로우를 구현해야한다.
0번 => 7번
1번 => 0번
2번 => 1번
3번 => 2번
4번 => 3번
5번 => 4번
6번 => 5번
7번 => 6번
i번째 톱니는 (i-1+8)%8번째 톱니의 자리로 이동하게 된다.

• 다음 위치로 이동시키기 위해서 -1을 해주고.
• -1 해주면서 음수로 떨어지는 언더플로우 발생시 맨뒤로 보내주기 위해서 전체 길이인 +8을 더해준다.
• 언더플로우를 구현시키기 위해서 %8을 해준다.

회전 코드

static void rotate(int gear, int direction) {
	int[] tempOrigin = gears[gear].clone();
	
	if(direction == 1) {
		for (int i = 0; i < tempOrigin.length; i++) {
			gears[gear][(i+1)%8] = tempOrigin[i]; 	// 임시로 저장해둔 원본에서 0번 위치는 1번으로 움직이고 1번 위치는 2번으로 움직여야한다. 
													// 이 규칙이 6번까지는 유지되지만, 7번은 0번으로 가야하므로 8로 나눈 나머지를 사용한다. 
													// 이렇게 하면 0~6번까지도 결과에 변화가 없다. 
		}
	} else { // direction == -1
		for (int i = 0; i < tempOrigin.length; i++) {
			gears[gear][(i-1+8)%8] = tempOrigin[i]; 	// 임시로 저장해둔 원본에서 0번 위치는 7번으로 움직이고, 나머지는 자기 위치보다 앞으로 움직인다. (0->7, 1->0,... 7->6)
		}
	}
}

그런데 회전방향이 1일때 +1을 해주고, -1일때 -1을 해주는 것에서 둘을 합칠수 있다는 생각이 들었다.
(i+1)%8 => (i+1+8)%8로 바꾸어도 +8은 %8로인해 0이 되기 때문에 지장이 안생긴다.
후의 회전전파 단계에서 회전하지 않는 기어들도 회전방향을 0으로 주어서 일괄적으로 회전시키는데, 이때도 지장없다.
.
만약 회전방향에 따라 코드를 분리한다고 하면, 회전전파 단계를 고려하여서
반시계방향으로 회전할때를 else가 아닌 else if (direction==-1)로 처리해주어야 한다.

향상된 회전 코드

static void rotate(int gear, int direction) {
	int[] tempOrigin = gears[gear].clone();
	for (int i = 0; i < tempOrigin.length; i++) {
		gears[gear][(i+direction+8)%8] = tempOrigin[i]; 
	}
}

톱니바퀴 회전 전파 구현

한 기어가 회전할때 어디까지 같이 회전하는지 미리 알아야한다.
기어는 동시에 회전하기 때문이다.
따라서 모든 기어의 회전방향을 배열에 담아서 기록한다.
.
따라서 선택된 기어를 기준으로 왼쪽 방향으로 전파시켜본다.
함께 돌아가지 않는 기어를 만날때까지 왼쪽으로 타고 넘어간다.
서로 반대 방향으로 기어가 회전하므로, 넘어갈때마다 회전 방향을 -1을 곱해줘야한다. 그리고 그 값을 배열 기록한다.
맨 왼쪽 기어인 0번 기어에 도착하면 더 이상 함께 돌아갈 기어가 없으므로 멈춘다.
.
위 과정을 오른쪽 방향으로 전파시킨다.
오른쪽으로 타고 넘어가면서 함께 회전하는 기어를 만날때마다 회전방향을 반대로(*-1) 해주고 그 값을 회전방향을 기록하는 배열에 기록한다.
함께 돌아가는 않는 기어를 만나거나, 맨 오른쪽 기어인 4번 기어에 도착하면.
더 이상 함께 돌아갈 기어가 없으므로 중단한다.
.
기어가 함께 돌아갈지 여부는 3번과 7번톱니의 극성이 같은지 여부로 판단한다.
.
왼쪽과 오른쪽으로의 전파가 끝났다면, 모든 기어의 회전방향을 파악한 상태이므로 모든 기어를 각자의 회전방향으로 회전시킨다.

회전 전파 코드

static void canRotateThenDo(int selectedGear, int direction) {
	int[] temp = new int[4];			// 각 기어의 회전방향은 0으로 초기화돼있음. 회전이 전파 안된 기어는 값이 0이라 회전안함.
	temp[selectedGear] = direction;
	
	// 오른쪽으로 확장(전파)
	int point = selectedGear; 			// 시작 기어의 위치 => 오른쪽으로 넘어갈때마다 +1돼야함.
	int nowDirection = direction;		// 시작 기어의 회전방향 => 오른쪽으로 넘어갈때마다 *-1돼야함.
	while(true) {
		if(point==4-1) 					// 4번 기어는 비교할 오른쪽 기어가 없기 때문에 반복문 탈출
			break;
		if(gears[point][3-1]!=gears[point+1][7-1]) { // 서로 다른 극이므로 오른쪽으로 넘어갈수 있음. 
			point +=1;
			nowDirection = nowDirection*-1;
			temp[point] = nowDirection;	// 회전이 전파된 기어자리에 회전방향 저장해두기.
		} else { 						// 회전이 전달안되므로 탈출
			break;
		}
	}
	
	// 왼쪽으로 확장(전파)
	point = selectedGear; 				// 시작 기어의 위치 => 왼쪽으로 넘어갈때마다 -1돼야함.
	nowDirection = direction;			// 시작 기어의 회전방향 => 왼쪽으로 넘어갈때마다 *-1돼야함.
	while(true) {
		if(point==1-1) 					// 1번 기어는 비교할 왼쪽 기어가 없기 때문에 반복문 탈출
			break;
		if(gears[point-1][3-1]!=gears[point][7-1]) { // 서로 다른 극이므로 왼쪽으로 넘어갈수 있음. 
			point -=1;
			nowDirection = nowDirection*-1;
			temp[point] = nowDirection;	// 회전이 전파된 기어자리에 회전방향 저장해두기.
		} else { 						// 회전이 전달안되므로 탈출
			break;
		}
	}
	
	// 전부 회전시키기.
	for (int i = 0; i < temp.length; i++) {
		rotate(i, temp[i]);
	}
}

전체 코드

import java.io.*;
import java.util.*;
public class BOJ_14891_톱니바퀴6 {
	// 입력고정
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	
	
	// 세팅
	static int[][] gears;
	static int[][] cmd; // 대상 톱니 / 회전 방향
	static int sum;
	static int K;
	
	// 메소드

	//// 회전 판정
	static void canRotateThenDo(int selectedGear, int direction) {
		int[] temp = new int[4];			// 각 기어의 회전방향은 0으로 초기화돼있음. 회전이 전파 안된 기어는 값이 0이라 회전안함.
		temp[selectedGear] = direction;
		
		// 오른쪽으로 확장(전파)
		int point = selectedGear; 			// 시작 기어의 위치 => 오른쪽으로 넘어갈때마다 +1돼야함.
		int nowDirection = direction;		// 시작 기어의 회전방향 => 오른쪽으로 넘어갈때마다 *-1돼야함.
		while(true) {
			if(point==4-1) 					// 4번 기어는 비교할 오른쪽 기어가 없기 때문에 반복문 탈출
				break;
			if(gears[point][3-1]!=gears[point+1][7-1]) { // 서로 다른 극이므로 오른쪽으로 넘어갈수 있음. 
				point +=1;
				nowDirection = nowDirection*-1;
				temp[point] = nowDirection;	// 회전이 전파된 기어자리에 회전방향 저장해두기.
			} else { 						// 회전이 전달안되므로 탈출
				break;
			}
		}
		
		// 왼쪽으로 확장(전파)
		point = selectedGear; 				// 시작 기어의 위치 => 왼쪽으로 넘어갈때마다 -1돼야함.
		nowDirection = direction;			// 시작 기어의 회전방향 => 왼쪽으로 넘어갈때마다 *-1돼야함.
		while(true) {
			if(point==1-1) 					// 1번 기어는 비교할 왼쪽 기어가 없기 때문에 반복문 탈출
				break;
			if(gears[point-1][3-1]!=gears[point][7-1]) { // 서로 다른 극이므로 왼쪽으로 넘어갈수 있음. 
				point -=1;
				nowDirection = nowDirection*-1;
				temp[point] = nowDirection;	// 회전이 전파된 기어자리에 회전방향 저장해두기.
			} else { 						// 회전이 전달안되므로 탈출
				break;
			}
		}
		
		// 전부 회전시키기.
		for (int i = 0; i < temp.length; i++) {
			rotate(i, temp[i]);
		}
	}
	
	//// 회전
	static void rotate(int gear, int direction) {
		int[] tempOrigin = gears[gear].clone();
		for (int i = 0; i < tempOrigin.length; i++) {
			gears[gear][(i+direction+8)%8] = tempOrigin[i]; 	// 8은 더해도 %8로 사라지는 부분이기 때문에 +1 로직에서도 정상적으로 작동한다. -1로직을 위해 +8을 하는 것이다.
		}
	}
	
	// 메인
	public static void main(String[] args) throws Exception {
		// 입력
		
		//// 기어 입력
		gears = new int[4][8];
		for (int i = 0; i < 4; i++) {
			char[] cList = input.readLine().toCharArray();
			for (int j = 0; j < cList.length; j++) {
				gears[i][j] = Character.getNumericValue(cList[j]);
			}
		}
		//// 커맨드 입력
		K = Integer.parseInt(input.readLine());
		cmd = new int[K][2];
		for (int k = 0; k < K; k++) {
			tokens = new StringTokenizer(input.readLine());
			cmd[k][0] = Integer.parseInt(tokens.nextToken()) -1;	// 기어번호를 인덱스번호와 맞춤.
			cmd[k][1] = Integer.parseInt(tokens.nextToken())   ;
		}
		// 세팅
		// 작업
		for (int i = 0; i < cmd.length; i++) {
			int selectedGear = cmd[i][0];
			int direction = cmd[i][1];
			canRotateThenDo(selectedGear, direction);
		}
		
		sum = 0;
		for (int i = 0; i < gears.length; i++) {
			if (gears[i][0] == 1){ // i번 기어의 12시 방향이 S극(1)이면 2의 i승을 더해준다.
				sum += (int) Math.pow(2,i);
			}
		}
		// 출력
		System.out.println(sum);
	}

}

퍼포먼스

[ 11,852 KB | 64 ms ]

마무리

컨디션이 안 좋아서 잔 실수를 많이했다. 컨디션 관리를 잘 하자...

// 인덱스값을 서로 바꿔서 넣었다.
static void rotate(int gear, int direction) {
	for (int i = 0; i < tempOrigin.length; i++) {
		gears[gear][i] = tempOrigin[(i+direction+8)%8]; 
	}
}

// 와일문 안에서 수정해가면서 사용할 변수를 와일문 안에서 선언했다...
// nowDirection = direction*-1; 가 아니라 
// nowDirection = nowDirection*-1; 이어야 한다.
static void canRotateThenDo(int gearSelcted, int direction) {
		int[] temp = new int[4]; // 0으로 초기화돼있음. 회전이 전파 안된 기어는 값이 0이라 회전안함.
		temp[gearSelcted] = direction;
		
		// 오른쪽으로 이동
		while(true) {
			int point = gearSelcted; 		// 시작 기어의 위치 => 오른쪽으로 확장될때마다 +1돼야함.
			int nowDirection = direction;	// 시작 기어의 회전방향 => 오른쪽으로 넘어갈때마다 *-1돼야함.
			if(point==4-1) // 4번 기어는 비교할 오른쪽 기어가 없기 때문에 반복문 탈출
				break;
			if(gears[point][3-1]!=gears[point+1][7-1]) { // 서로 다른 극이므로 오른쪽으로 넘어갈수 있음. 
				nowDirection = direction*-1;
				point +=1;
				temp[point] = nowDirection;	// 회전이 전파된 기어의 회전방향 저장해두기.
			} else { // 회전이 전달안되므로 탈출
				break;
			}
		}