(JAVA) 백준 14891번 : 톱니바퀴

 

 

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

14891번: 톱니바퀴

 

정말 오랜만에 백준을 풀었다.

 

회사에서 프로젝트에 지원가면서 개발하며 적응하느라

 

집에서 문제 풀 수 없었다고 한다...!!

 

하지만 이제 적응도 했고

 

개발도 어느정도 맞춰갈 수 있어서

 

슬슬 백준에 시동건다!

 

 

 

이 문제는 시뮬레이션 문제로

 

규칙을 찾아 알고리즘을 짠 후 

그거대로 코딩하면 된다.

 

 

내 알고리즘의 핵심은

 

1) 톱니바퀴 톱니를 나타내기 위해 LinkedList 배열 및 LinkedList<Character> 사용

2) 처음 움직인 톱니 위치부터 좌우로 뻗어나가며 반대 방향으로 이동할 수 있는 바퀴 탐색

 

이다.

 

 

 

 

매커니즘

---

하단의 소스코드에서 각 알고리즘 별로 주석을 달아놓았다.

 

따라서, 소스볼 때 이해하기 편할 수 있을 것이다.. :)))

 

 

 

 

큰 알고리즘은

 

 

 

1)  톱니바퀴의 톱니 입력 값을 톱니바퀴 순서대로 LinkedList[4] 의 인덱스에 맞게 LinkedList<Character>에 넣어준다.

 

 

2)  해당하는 값이 들어갈 수 있게 배열을 생성한다.

 

|  1  |  2  |  3  |  4        <= 톱니바퀴 번호(index)

|  0  |  0  |  -1 |  0        <= 회전 방향 (1: 시계 방향, 0: 정지, -1: 반시계. int 배열)

|  F  |  F  |  T  |  F         <= 톱니바퀴 회전 체크 여부(boolean 배열)

 

 

3)  처음 회전한 톱니바퀴의 인덱스 Queue에 넣기. 해당 톱니바퀴의 방향과 체크 여부 설정.

 

 

4)  Queue에서 꺼낸 톱니바퀴 위치에서 인덱스 -1(왼쪽), 인덱스 + 1(오른쪽) 톱니바퀴 비교

 

 ** 인덱스 + 1 이면 해당 인덱스 톱니바퀴의 2번 톱니와 인덱스 +1의 6번 톱니 비교

 ** 인덱스 - 1 이면 해당 인덱스 톱니바퀴의 6번 톱니와 인덱스 -1의 2번 톱니 비교

 ** 값이 다르면 인덱스 톱니바퀴의 반대 방향 배열에 넣기. Queue에 넣기.

 

 

5)  Queue가 Empty 전까지 4) 반복

 

 

6)  회전 횟수 K번 3) ~ 5) 반복 진행

 

 

7)  점수 계산. 계산 시 Math.pow(2, index) 를 더하며 진행(점수 규칙이 2의 index제곱이므로)

 

 

 

 

 

감사합니다.

 

 

 

소스코드

---

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.Arrays;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.StringTokenizer;
	// 톱니바퀴 문제
	// 시뮬레이션
	public class p14891 {
	@SuppressWarnings("rawtypes")
	static LinkedList[] gears; // 바퀴들(0 ~ 3 : 1번부터 4번까지)
	static int[][] moves;
	static boolean[] checked;
	static int[] directions; // 1 : 시계방향, 0 : 정지, -1 : 반시계
	@SuppressWarnings("unchecked")
	public static void main(String args[]) throws IOException {
	gears = new LinkedList[4];
	checked = new boolean[4];
	directions = new int[4];
	for(int i = 0; i < 4; i++) {
	gears[i] = new LinkedList<Character>();
	}
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st;
	// 바퀴 만들기
	for(int i = 0; i < 4; i++) {
	st = new StringTokenizer(br.readLine());
	char[] gear = st.nextToken().toCharArray();
	for(char ch : gear) {
	gears[i].add(ch);
	}
	}
	// 회전 바퀴 및 방향 넣기
	st = new StringTokenizer(br.readLine());
	int k = Integer.valueOf(st.nextToken());
	moves = new int[k][2]; // 0 : 톱니바퀴 번호, 1 : 톱니바퀴 방향
	for(int i = 0; i < k; i++) {
	st = new StringTokenizer(br.readLine());
	int num = Integer.valueOf(st.nextToken());
	int direction = Integer.valueOf(st.nextToken());
	moves[i][0] = num - 1; // 인덱스 0 ~ 3
	moves[i][1] = direction;
	Arrays.fill(checked, false);
	Arrays.fill(directions, 0);
	move(moves[i][0], moves[i][1]);
	}
	// 점수 계산
	int sum = 0;
	for(int i = 0; i < 4; i++) {
	if(gears[i].get(0).equals('1')) {
	sum += Math.pow(2, i);
	}
	}
	System.out.println(sum);
	}
	// 각 톱니바퀴 이동방향 찾는 함수
	static void move(int gearIndex, int direction) {
	Queue<Integer> q = new LinkedList<Integer>(); // 바퀴 인덱스만 담김.
	checked[gearIndex] = true;
	directions[gearIndex] = direction;
	q.add(gearIndex);
	while(!q.isEmpty()) { // 바퀴 방향은 큐에 들어가기 전에 정해져있음.
	int index = q.poll();
	// 왼쪽
	if(index - 1 >= 0) {
	if(!checked[index - 1]) {
	// 왼쪽 바퀴의 3시 방향 바퀴축과 현재 바퀴의 9시 방향 바퀴축과 비교해서 다르면 반대 방향. 같으면 정지
	if(!gears[index - 1].get(2).equals(gears[index].get(6))) {
	directions[index - 1] = getThisGearDirection(directions[index]);
	checked[index - 1] = true;
	q.add(index - 1);
	}
	}
	}
	// 오른쪽
	if(index + 1 <= 3) {
	if(!checked[index + 1]) {
	// 오른쪽 바퀴의 9시 방향 바퀴축과 현재 바퀴의 3시 방향 바퀴축과 비교해서 다르면 반대 방향. 같으면 정지
	if(!gears[index + 1].get(6).equals(gears[index].get(2))) {
	directions[index + 1] = getThisGearDirection(directions[index]);
	checked[index + 1] = true;
	q.add(index + 1);
	}
	}
	}
	}
	change();
	}
	// 반대 방향 리턴
	static int getThisGearDirection(int direction) {
	if(direction == 1) {
	return -1;
	}
	return 1;
	}
	// 각 톱니바퀴 방향대로 이동
	static void change() {
	for(int i = 0; i < 4; i++) {
	switch(directions[i]) {
	case 1: // 시계 방향
	gears[i].add(0, gears[i].remove(gears[i].size() - 1));
	break;
	case 0:
	break;
	case -1: // 반시계 방향
	gears[i].add(gears[i].remove(0));
	break;
	}
	}
	}
	}

view raw p14891.java hosted with ❤ by GitHub