백준 14891번: 톱니바퀴

문제 설명

• https://www.acmicpc.net/problem/14891
• 4개의 톱니바퀴가 주어집니다.
• K번 톱니바퀴를 돌립니다.
• 회전하는 톱니바퀴 옆에 있는 톱니바퀴는 서로의 맞닿은 부분의 극값이 반대면 회전합니다.
  • 이때 맞닿은 톱니바퀴는 옆의 톱니바퀴와 반대방향으로 회전합니다.

접근법

• List에 톱니바퀴 데이터를 담았습니다. [톱니1,톱니2,톱니3,톱니4]
• 톱니의 회전, 연쇄회전여부는 반복적으로 활용되는 부분이기 때문에 메서드로 구현했습니다.
• addfirst,addlast,pollfirst,polllast의 기능(Deque)과 배열의 값에서 index로 접근하는 기능이(LinkedList) 필요합니다.
  • Deque에서 index로의 접근은 불가능하지만 LinkedList에서 first,last기능구현은 가능했기 때문에 LinkedList를 사용했습니다.
• 인접한 톱니바퀴를 확인하는 과정에서 무한루프가 발생할 수 있어 이를 방지하는 Checked 배열을 만들었습니다.

pseudocode

Main(){
    for(N번동안){
        Turn(처음 주어진 톱니를, 처음 주어진 방향으로);
        Checked변수 초기화;
    }
    점수를 확인합니다.
}

Turn(현재 톱니,방향){
	Splash() //현재 톱니의 왼쪽 혹은 오른쪽이 연쇄적으로 돌게 된다면 이들도 재귀적으로 Turn을 실행합니다.
    if(방향이 시계방향){
    	TurnClockWise();
    }else{
    	TurnCounterClockWise();
    }
}

TurnClockWise(톱니){
	톱니의 맨 뒤에 값을 가장 앞으로 옮깁니다.
}

TurnCounterClockWise(톱니){
	톱니의 가장 앞의 값을 맨 뒤로 옮깁니다.
}

Splash(현재톱니, 방향){
	if(현재톱니의 왼쪽 톱니를 아직 확인하지 않았다면{
    	해당 톱니를 체크했다는 표시를 남깁니다.
        if(맞닿은 방향이 달라 회전시킬 수 있다면){
        	Turn(); // 현재톱니와 반대방향으로 왼쪽 톱니를 회전시킵니다.
        }
    }
	if(현재톱니의 오른쪽 톱니를 아직 확인하지 않았다면{
    	해당 톱니를 체크했다는 표시를 남깁니다.
        if(맞닿은 방향이 달라 회전시킬 수 있다면){
        	Turn(); // 현재톱니와 반대방향으로 오른쪽 톱니를 회전시킵니다.
        }
    }
    
}

정답

import java.util.*;
import java.io.*;

public class Main {
	static List<Character>[] Gear; // index로 2번과 6번에 접근하기 위해 Deque가 아닌 lst를 썼습니다.
	static boolean[] Checked = new boolean[4];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Gear = new LinkedList[4];
		StringTokenizer st;
		for (int i = 0; i < 4; i++) {
			char[] chars = br.readLine().toCharArray();
			Gear[i] = new LinkedList<Character>();
			for (int j = 0; j < 8; j++) {
				Gear[i].add(chars[j]);
			}
		}

		int N = Integer.parseInt(br.readLine());
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int StartGearNum = Integer.parseInt(st.nextToken());
			boolean IsClockWise = (Integer.parseInt(st.nextToken()) == 1) ? true : false;
			Turn(StartGearNum - 1, IsClockWise);
			Arrays.fill(Checked, false);

		}

		System.out.println(Score());

	}

	public static void Turn(int index, boolean direction) {
		Checked[index] = true;
		Splash(index, direction); // 톱니를 돌리기 전에 맞닿은 톱니의 확인을 먼저 해줘야 합니다.
		if (direction) {
			TurnClockWise(Gear[index]);
		} else {
			TurnCounterClockWise(Gear[index]);
		}

	}

	public static void TurnClockWise(List<Character> lst) {
		char temp = lst.remove(lst.size() - 1); // pollLast
		lst.add(0, temp); // addFirst

	}

	public static void TurnCounterClockWise(List<Character> lst) {
		char temp = lst.remove(0); // pollFirst
		lst.add(temp); // addLast

	}

	public static void Splash(int now, boolean direction) {
		// 왼쪽
		if (0 <= now - 1 && !Checked[now - 1]) {
			Checked[now - 1] = true;
			if (Gear[now - 1].get(2) != Gear[now].get(6)) {
				Turn(now - 1, !direction);
			}
		}
		// 오른쪽
		if (now + 1 < 4 && !Checked[now + 1]) {
			Checked[now + 1] = true;
			if (Gear[now].get(2) != Gear[now + 1].get(6)) {
				Turn(now + 1, !direction);
			}

		}
	}

	public static int Score() {
		int score = 0;
		for (int i = 0; i < Gear.length; i++) {
			if (Gear[i].get(0) == '1')
				score += Math.pow(2, i);
		}
		return score;
	}
}

기타

아쉬운점

• Turn메서드 내에서 현재 톱니의 회전보다 Splash의 확인이 먼저 일어납니다. 재귀적으로 Turn이 호출되기 때문에 현실에서의 로직과는 다르게 가장 먼 톱니부터 먼저 돌리게 됩니다.
  • 예) 3번톱니에 의해 2,4번이 회전하고 2번에 의해 1번이 회전하는 상황이라고 할 때,
    제 코드는 현실의 논리인 3 > 2,4 > 1 순서가 아닌 1 > 2,4 > 3로 회전하게 됩니다.
  • 현재 톱니를 돌린 후 Splash를 실행하려면 맞닿은 부분이 달라지기 때문에 2,6번이 아닌 해당 이빨을 고려하는 작업이 필요합니다.
• Deque대신 ArrayList를 사용하는 게 맞을까?
  • Deque는 덱의 자료구조적인 특성에 의해 .get(index)메서드가 없는 걸로 알고 있습니다. 그렇다고해서 ArrayList의 add/remove를 0과 마지막 인덱스로 구현한 게 가장 효율적인 방법인지 잘 모르겠습니다.