[백준] 14891번 톱니바퀴

문제

총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.

이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다.

톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 예를 들어, 아래와 같은 경우를 살펴보자.

두 톱니바퀴의 맞닿은 부분은 초록색 점선으로 묶여있는 부분이다. 여기서, 3번 톱니바퀴를 반시계 방향으로 회전했다면, 4번 톱니바퀴는 시계 방향으로 회전하게 된다. 2번 톱니바퀴는 맞닿은 부분이 S극으로 서로 같기 때문에, 회전하지 않게 되고, 1번 톱니바퀴는 2번이 회전하지 않았기 때문에, 회전하지 않게 된다. 따라서, 아래 그림과 같은 모양을 만들게 된다.

위와 같은 상태에서 1번 톱니바퀴를 시계 방향으로 회전시키면, 2번 톱니바퀴가 반시계 방향으로 회전하게 되고, 2번이 회전하기 때문에, 3번도 동시에 시계 방향으로 회전하게 된다. 4번은 3번이 회전하지만, 맞닿은 극이 같기 때문에 회전하지 않는다. 따라서, 아래와 같은 상태가 된다.

톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.

다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

출력

총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.

• 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
• 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
• 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
• 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

 

사실 이 문제는 구현하라고 하면 쉬운 문제다.

하지만, 문제는 구현한다는건 쉬운게 아니라는 거다. 그래서 해맸다.

내가 왜 이 문제를 틀렸을까? 곰곰히 생각해봤다.

 

이유는 크게 2가지다.

 

  첫 번째 이유 : 톱니바퀴를 회전할때 다른 톱니 바퀴를 고려하지 않았다.

  두 번째 이유 : 톱니바퀴의 위치를 고려하지 못했다.

 

 

 내가 전에 작성했던 코드를 보면서 어떤 문제가 있었는지 이야기 해보자.

import java.io.IOException;
import java.util.Scanner;

public class Main {

	static String rightS(String wr) {
		String righto = wr.charAt(wr.length() - 1) + "";

		for (int i = 0; i < wr.length() - 1; i++) {
			righto += wr.charAt(i);
		}

		return righto;
	}

	static String leftS(String wr) {
		String lefto = "";

		for (int i = 1; i < wr.length(); i++) {
			lefto += wr.charAt(i);
		}

		return lefto + wr.charAt(0);
	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);

		String wheel[] = new String[4];

		for (int i = 0; i < 4; i++) {
			wheel[i] = sc.nextLine();
		}

		int k = sc.nextInt();

		while (k-- > 0) {
			int w = sc.nextInt();
			int h = sc.nextInt();

			if (h == 1) {
				wheel[w - 1] = rightS(wheel[w - 1]);

			} else if (h == -1) {
				wheel[w - 1] = leftS(wheel[w - 1]);

			}
			
			if (w < 4 && wheel[w].charAt(2) != wheel[w-1].charAt(2)) {
				wheel[w] = rightS(wheel[w]);
			}
		}
		
		int count = 0;
		
		if (wheel[0].charAt(0) == '1') {
			count += 1;
		}
		
		if (wheel[1].charAt(0) == '1') {
			count += 2;
		}
		
		if (wheel[2].charAt(0) == '1') {
			count += 4;
		}
		
		if (wheel[3].charAt(0) == '1') {
			count += 8;
		}
		
		System.out.println(count);

	}
}

오른쪽, 왼쪽 회전 시키는건 좋았다. 하지만 그들은 처음 도는 톱니바퀴만 돌고 있다. 그리고 2 == 2부분인데 이건 그냥 실수다. 6으로 한다고 해도 답이 아니겠지만.. 왜냐하면 오른쪽으로 돌고 끝이다.

위에 그림 하나를 복사해 보자.

 

 

이 그림인데 인덱스를 붙여서 확인해 보자.  왼쪽 부터 0 1 2 3

 

그럼 생각해보자. 0번이 회전하면 1번이 회전할수도 안할 수 도 있다.

이렇게 계속 생각해보면 1번이 회전할때는 0번, 2번이...

이런식으로 간다.

 

그러니까 무조건 회전한다의 가정하에

 

0 ->  1 

0 <- 1 -> 2

1 <- 2 -> 3

2 <- 3 

 

이런 그림이 완성된다.

 

이제 번호를 생각해보자.  0번이 1번을 돌린다고 생각해보자.

 

그럼 다시 위의 그림이 필요할듯 싶다.

 

이제 12시를 기준부터 시작해서 0을 넣어보자.

그러니까 12시가 0번이다. 그러면 인덱스가 0 1 2 3 4 5 6 7 이 나온다.

 

이제 그림을 보면서 숫자를 새보자. 인접하다는 이야기가 무엇일까? 그냥 옆에 있다는 소리다.

사실 내가 이해력이 낮아서 인접이라는게 사실 와닿지는 않는다.

 

문제에 서로 인접한 톱니바퀴가 서로 다른 극일때 회전한다고 적혀있다.

그러면 0번은 2가 되고, 1번은 6번이 된다.

 

근데 중요한건 이게 전부가 아니라는 이야기다. 이건 또 무슨 소리냐면

아까 인접하다는게 옆에 있다고 했다. 그렇다는 건 만약, 1번을 돌렸을때,

0번 2번을 돌려야 한다고 했다. 그러면

0번은 2 1번은 6 이지만

1번은 2 2번은 6이된다. 이렇다는 건.  한 가지 방법만 생각하는것이 아니라 양쪽 모두 생각해야한다.

그렇지않으면 절대로 풀 수 없는 문제가 된다.

 

여기서 규칙 하나 찾을 수 있다.

왼쪽일 때는 무조건 2번이고 오른쪽 돌릴때는 6번이 기준이 된다. 이것을 구현에 따라 달라 지겠지만... 아무튼 이게 베이스다.

 

이제 다음으로 생각해야될 문제는

1번 회전하고 끝이 아니다. 시작 톱니가 아니여도 계속해서 다르면 돌려줘야한다.

이걸 못해서 나는 틀렸다.

 

모 블로그의 도움을 받아 작성할 수 있었고,

까먹을 수 있기 때문에 블로그에 작성하려고한다.

 

package _2020_06_01.B;

import java.util.Scanner;

class Main {
	static String[] node = new String[4];

	static void rotate(int index, int arrow) {
		
		String t = node[index];
		if (arrow == 1) {
			String temp = t.charAt(t.length() - 1) + "";
			for (int i = 0; i < t.length() - 1; i++) {
				temp += t.charAt(i);
			}
			node[index] = temp;
		}

		if (arrow == -1) {
			String temp = "";
			for (int i = 1; i < t.length(); i++) {
				temp += t.charAt(i);
			}
			temp += t.charAt(0);
			node[index] = temp;
		}

	}

    
	static void left(int index, int arrow) {
        // 인덱스가 -1이면 여기서 해결됨...
		if (index < 0)
			return;

		if (node[index].charAt(2) != node[index + 1].charAt(6)) {
			left(index - 1, -arrow);
			rotate(index, arrow);
		}
	}

	static void right(int indedx , int arrow) {
        // 인덱스가 3이상이면 여기서 해결됨
		if (indedx > 3) return;
		
		if (node[indedx].charAt(6) != node[indedx-1].charAt(2)) {
			right(indedx+1, -arrow);
			rotate(indedx, arrow);
		}
	}
	

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		for (int i = 0; i < 4; i++) {
			node[i] = sc.nextLine();
		}

		int k = sc.nextInt();

		while (k-- > 0) {
			int index = sc.nextInt();
			int arrow = sc.nextInt();
			
			index--;
			
			left(index - 1, -arrow);
			right(index+1, -arrow);
			rotate(index, arrow);	
			
		}
		
		
		int ans = 0;
		if (node[0].charAt(0) == '1') {
			ans += 1;
		}
		
		if (node[1].charAt(0) == '1') {
			ans += 2;
		}
		
		if (node[2].charAt(0) == '1') {
			ans += 4;
		}
		if (node[3].charAt(0) == '1') {
			ans += 8;
		}
		
		System.out.println(ans);

	}
}

 이게 내 소스인데 나는 조금 특이게하게 했다. 보통은 이중배열을 사용해서 해결했지만 문자열이 편할거라 생각했다.

 

회전 시킨 방법에 대해 설명하면

예를들어 1 2 3 4 5 6 이라는 문자열이 있다고 가정하자.

 

그러면 시계 방향으로 돌린다고 하면 6 1 2 3 4 5 가 된다. 뭐가 이상하지 않나.

맞다. 그냥 6이 앞으로 튀어 나왔다. 나는 이 부분을 미리 temp로 저장시켜놓고, 인덱스 0번부터  길이의 -1까지 전부 더해 준다. 그러면  6 1 2 3 4 5가 되는데 

 

이건 temp이므로 원래 배열값에 넣어주면 완벽하게 시계방향으로 돌려지게 된다.

 

그러면 반시계 방향은 어떻게 될까?

1 2 3 4 5 6 -> 2 3 4 5 6 1 이된다.

그러니까 맨처음것을 맨뒤로 보내주면 된다. 이건 바로 해도 될수 있을지도 모르지만,

바로 하면 배열값에 추가되기 때문이기도 하지만, 배열이 바뀔 수 있다. 그렇기 때문에 temp로 시작했다.

아까는 0부터 length-1까지 반복했다면 이번에는 1부터 끝까지 반복했다.

그리고 temp에 맨처음값을 추가해주면 된다.

역시 이 부분도 원래 배열로 바꿔치기 해주면 된다.

 

이 부분은 구현하는 사람 마음이지만

비트 마스크인가 머시기를 사용할 수 도 있고,

덱이라는 자료구조를 사용할 수 도 있고,

이중 배열로 사용할 수도 있다.

 

나는 스트링으로 해결했다.

 

마지막 점수 계산은 할 줄몰라서 그냥 이렇게 했다.