BOJ 백준 14891 톱니바퀴

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

 

 

[ 문제 요약 ]

• 총 8개의 톱니를 갖고 있는 톱니바퀴 4개가 일렬로 놓여 있습니다.
• 각 톱니바퀴의 톱니는 N, S 극 중 하나입니다.
• 톱니바퀴는 왼쪽부터 1,2,3,4번을 갖습니다.
• 톱니를 총 k 번 회전시키며, 회전은 시계 방향과 반시계 방향으로 가능합니다.
• A 톱니바퀴가 시계방향으로 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르면 B는 반시계 반향으로 회전합니다. B와 맞닿은 C도 B와 극이 다르면 이번에 C는 시계방향으로 회전합니다. 극이 같으면 회전하지 않습니다.
• 극이 같은지 다른지는 돌리고 난 후가 아니라 돌리기 전 상태로 파악합니다.
• 톱니의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어질 때, 최종 톱니바퀴의 상태를 점수로 산정해 출력합니다.
• 1번 톱니바퀴의 12시 방향이 N 극이면 0점, S 극이면 1점
• 2번 톱니바퀴의 12시 방향이 N 극이면 0점, S 극이면 2점
• 3번 톱니바퀴의 12시 방향이 N 극이면 0점, S 극이면 4점
• 4번 톱니바퀴의 12시 방향이 N 극이면 0점, S 극이면 8점

 

 

[ 테스트 케이스 설명 ]

10101111// 1번 톱니의 상태(8개의 정수로 이뤄져있으며 12시 방향부터 시계방향 순으로 주어짐)
01111101// 2번 톱니의 상태(N극은 0, S극은 1)
11001110// 3번 톱니의 상태
00000010// 4번 톱니의 상태
2 // 회전 횟수(1<=100)
3 -1// 회전시킨 톱니바퀴의 번호 : 방향(1은 시계, -1은 반시계)
1 1
K번 회전시킨 후 네 톱니바퀴의 점수의 합을 출력한다 : 7

 

[ 알고리즘 분류 ]

• 구현
• 시뮬레이션

 

[ 문제 해설 ]

 

특정 톱니바퀴가 회전한 후 그 결과를 이용해 이웃 톱니바퀴의 회전을 구하는 것이 아니라, 회전 전의 상태로 회전할 톱니바퀴를 구해야 합니다.

그래서 회전 전에 톱니마다 어디로 회전해야 하는지 먼저 구한 후 회전 시켜주면 되는 간단한 구현 문제입니다.

 

코드는 두 가지 방식을 보여줍니다.

 

1. 일반 for 문을 사용한 방법
2. 재귀를 사용한 방법

 

[ 정답 코드 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main{
	
	static final int LEFT = -1;// 반시계 방향
	static final int RIGHT = 1;// 시계 방향
	static final int S = 1;// S극은 1로 입력
	static int sawTooth[][];// 톱니바퀴 마다의 극 저장
	static int changeDir[];// 각 톱니바퀴의 회전 방향 저장
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		sawTooth = new int[5][8];
		changeDir = new int[5];
		
		for(int i=1; i<=4; i++)
		{
			String str = br.readLine();
			for(int j=0; j<str.length(); j++)
				sawTooth[i][j] = str.charAt(j) - '0';
		}
		
		int K = Integer.parseInt(br.readLine());
		
		while(K-->0)
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			int idx = Integer.parseInt(st.nextToken());
			changeDir[idx] = Integer.parseInt(st.nextToken());
			
			dirMark(idx);// 초기 입력을 기준으로 회전해야할 모든 톱니바퀴의 방향 세팅
			change();// 그대로 회전
		}
		
		print();// 결과 출력
	}
	static void dirMark(int idx) {
		// 왼쪽 마킹
		for(int i=idx - 1, dir = changeDir[idx]; i>=1; i--)
		{
			int l = sawTooth[i][2];// 왼쪽 톱니바퀴
			int r = sawTooth[i + 1][6];// 오른쪽 톱니바퀴
			
			dir = -dir;// 방향은 항상 반전
			
			if(l != r)// 다르면 방향 입력 및 연산 지속
			{
				changeDir[i] = dir;
				continue;
			}
			break;
		}
		// 오른쪽 마킹
		for(int i=idx + 1, dir = changeDir[idx]; i<=4; i++)
		{
			int l = sawTooth[i - 1][2];
			int r = sawTooth[i][6];
			
			dir = -dir;// 방향은 항상 반전
			
			if(l != r)// 다르면 방향 입력 및 연산 지속
			{
				changeDir[i] = dir;
				continue;
			}
			break;
		}
	}
	static void change() {
		for(int i=1; i<=4; i++)
		{
			if(changeDir[i] == LEFT)
				turnLeft(i);
			else if(changeDir[i] == RIGHT)
				turnRight(i);
			
			changeDir[i] = 0;// 이동 방향 초기화
		}
	}
	static void turnLeft(int idx) {
		int arr[] = sawTooth[idx];
		int first = arr[0];
		
		for(int i=1; i<=7; i++)
			arr[i-1] = arr[i];
		
		arr[7] = first;
	}
	static void turnRight(int idx) {
		int arr[] = sawTooth[idx];
		int last = arr[7];
		
		for(int i=7; i>=1; i--)
			arr[i] = arr[i-1];
		
		arr[0] = last;
	}
	static void print() {
		int res = 0;
		
		for(int i=1; i<=4; i++)
			if(sawTooth[i][0] == S)
			{
				res += i;
				if(i == 3) res += 1;
				if(i == 4) res += 4;
			}
		
		System.out.print(res);
	}
}

 

 

[ 재귀 방법 ]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main{
	
	static final int LEFT = -1;// 반시계 방향
	static final int S = 1;// S극은 1로 입력
	static int sawTooth[][];// 톱니바퀴 마다의 극 저장
	
	public static void main(String[] args)throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		sawTooth = new int[5][8];
		
		for(int i=1; i<=4; i++)
		{
			String str = br.readLine();
			for(int j=0; j<str.length(); j++)
				sawTooth[i][j] = str.charAt(j) - '0';
		}
		
		int K = Integer.parseInt(br.readLine());
		
		while(K-->0)
		{
			StringTokenizer st = new StringTokenizer(br.readLine());
			int idx = Integer.parseInt(st.nextToken());
			int dir = Integer.parseInt(st.nextToken());
			leftCheck(idx - 1, dir);// dfs로 왼쪽 톱니바퀴 탐색 및 회전
			rightCheck(idx + 1, dir);// dfs로 오른쪽 톱니바퀴 탐색 및 회전
			turn(idx, dir == LEFT);// 현재 톱니 회전
		}
		
		print();// 결과 출력
	}
	static void rightCheck(int idx, int dir) {
		int nowDir = -dir;
		
		if(idx == 5)return;
		if(sawTooth[idx - 1][2] == sawTooth[idx][6])return;
		
		rightCheck(idx + 1, nowDir);
		
		turn(idx, nowDir == LEFT);
	}
	static void leftCheck(int idx, int dir) {
		int nowDir = -dir;
		
		if(idx == 0)return;
		
		if(sawTooth[idx][2] == sawTooth[idx + 1][6])return;
		
		leftCheck(idx - 1, nowDir);
		
		turn(idx, nowDir == LEFT);
	}
	static void turn(int idx, boolean isLeft) {
		int arr[] = sawTooth[idx];
		if(isLeft)
		{
			int first = arr[0];
			
			for(int i=1; i<=7; i++)
				arr[i-1] = arr[i];
			
			arr[7] = first;
			return;
		}
		
		int last = arr[7];
		
		for(int i=7; i>=1; i--)
			arr[i] = arr[i-1];
		
		arr[0] = last;
	}
	static void print() {
		int res = 0;
		
		for(int i=1; i<=4; i++)
		{
			if(sawTooth[i][0] == S)
			{
				res += i;
				if(i == 3) res += 1;
				if(i == 4) res += 4;
			}
		}
		System.out.print(res);
	}
}

 

[ 여러 반례들 ]

10001011
10000011
01011011
00111101
5
1 1
2 1
3 1
4 1
1 -1
답 : 6
10010011
01010011
11100011
01010101
8
1 1
2 1
3 1
4 1
1 -1
2 -1
3 -1
4 -1
답 : 5
01100110
10001111
00011000
10111000
3
3 -1
3 1
1 1
답 : 2
00100001
11111101
10000000
00000000
1
3 1
답 : 3