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

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

15662번: 톱니바퀴 (2)

 

난이도 : 실버 2

 

문제가 많이 깁니다. 문제의 길이와 친절함은 대부분 비례합니다.

 

문제를 정리해보자면 

각 톱니바퀴는 8개의 톱니를 가지고 있고 T개의 톱니바퀴가 주어집니다.

12시부터 시계방향으로 톱니의 상태가 주어지고(1-S, 0-N)

톱니는 1번부터 T번까지입니다.

 

톱니는 회전 방향이 1일 때 시계방향, -1일 때 반시계 방향입니다.

양 옆의 톱니가 맞닿아있는 부분이 같다면 옆의 톱니는 지정된 톱니 회전 방향의 반대로 회전합니다.

지정 톱니 1번 회전 당 최대 회전 횟수는 1번입니다.(회전 후 맞닿은 톱니가 같아도 더 회전하지 않습니다.)

 

저는 톱니 1번부터 T번을 LinkedList[]를 사용하여 톱니의 상태를 관리했습니다.

 

 

톱니의 회전을 리스트 값으로 설명하겠습니다.

톱니가 반시계 방향으로 회전하는 경우에는 첫 원소가 가장 끝으로 갔습니다.

톱니가 시계방향으로 회전하는 경우에는 마지막 원소가 가장 처음으로 갔습니다.

반시계 : ll[number].addLast(ll[number].removeFirst());

시계   :  ll[number].addFirst(ll[number].removeLast()); 

 

이렇게 표현할 수 있습니다.

 

주의할 점은 톱니바퀴를 회전하기 전 양 옆의 톱니바퀴를 먼저 회전시켜야 합니다.

이것은 재귀로 구현했습니다.

---

전역 변수 

t = 톱니바퀴의 수ll[] = 톱니바퀴의 톱니 상태를 저장하는 LinkedList

메소드

void main 

입력 값을 받고 톱니 상태를 저장한 후 k번 회전을 합니다. (rotate, count 호출)

void rotate

양 옆의 톱니바퀴를 회전시켜야 하는지 조건을 따진 후 참이라면 그 톱니바퀴부터 회전시킵니다.

양 옆의 톱니바퀴를 회전시킨 후 본 톱니바퀴를 회전시킵니다. (diff 호출) 

boolean diff

현재 톱니바퀴의 양 옆에 있는 톱니바퀴를 회전시켜야 하는지 검사합니다.

현재 톱니바퀴가 1번째, T번째이거나 옆 톱니가 같다면 false를 반환합니다.

int count

12시 방향이 S(ll[n].get(0) == 1)인 개수를 센 후 반환합니다.

 

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

public class p15662 {
	static int t;
	static LinkedList ll[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz;
		String s;
		t = Integer.parseInt(br.readLine());
		ll = new LinkedList[t+1];

		for(int i = 1; i <= t; i++) {
			s = br.readLine();
			ll[i] = new LinkedList<Integer>();
			for(int j = 0; j < s.length(); j++)
				ll[i].add(s.charAt(j)-'0');
		}

		int k = Integer.parseInt(br.readLine());
		for(int i = 0; i < k; i++) {
			stz = new StringTokenizer(br.readLine());
			int number = Integer.parseInt(stz.nextToken());
			int dir = Integer.parseInt(stz.nextToken());

			rotate(number, dir, 2);
		}

		System.out.println(count());
	}

	//right 값으로 왼쪽, 오른쪽, 양 옆(초기 값 2)으로 검사합니다.
	public static void rotate(int number, int clock, int right) {
		
		if(clock == 1)
			clock = -1;
		else
			clock = 1;

		//오른쪽으로 검사
		if(right == 1 || right == 2)
			if(diff(number, true)) {
				rotate(number+1, clock, 1);
			}
        //왼쪽으로 검사
		if(right == 0 || right == 2)
			if(diff(number, false))
				rotate(number-1, clock, 0);

		//시계방향 회전
		if(clock == -1)
			ll[number].addFirst(ll[number].removeLast());
        //반시계방향 회전
		else
			ll[number].addLast(ll[number].removeFirst());

	}

	public static boolean diff(int number, boolean right) {
		if(right) {
			if(number == t)
				return false;

			if(ll[number].get(2) == ll[number+1].get(6))
				return false;
		}
		else {
			if(number == 1)
				return false;

			if(ll[number].get(6) == ll[number-1].get(2))
				return false;
		}

		return true;
	}

	public static int count() {
		int count = 0;

		for(int i = 1; i <= t; i++) 
			if((int)ll[i].get(0) == 1)
				count++;

		return count;
	}

}