백준 14891 톱니바퀴 (Java)

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

1. 문제

총 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. 풀이

조금은 복잡한 구현 문제였다. 차근차근 풀어보자.

        List<String> wheels = new ArrayList<>();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer;

        //index 통일용
        wheels.add("");

        for (int i = 1; i <= 4; i++) {
            wheels.add(reader.readLine());
        }

        int k = Integer.parseInt(reader.readLine());

        for (int i = 0; i < k; i++) {

            tokenizer = new StringTokenizer(reader.readLine());

            int w = Integer.parseInt(tokenizer.nextToken());        //회전 시킬 톱니바퀴
            int dir = Integer.parseInt(tokenizer.nextToken());      //회전 밤향(1: 시계, -1, 반시계)

            boolean[] visit = new boolean[5];

우선 현재 톱니의 상태를 입력받아 저장한다. 톱니바퀴 회전은 one indexed로 받으므로 리스트의 맨 앞에 빈 문자열을 추가해주었다. 또, 각 회전에 대해 회전할 톱니의 번호와 방향을 입력받는다. 여기서는 bfs로 모든 톱니의 회전을 확인할 것이므로 visit 배열을 선언해주었다.

            //현재 톱니바퀴로부터 bfs
            Queue<Pair> qu = new ArrayDeque<>();

            qu.offer(new Pair(w, dir));
            visit[w] = true;

            while (!qu.isEmpty()) {

                Pair cur = qu.poll();

                //현재 톱니바퀴를 방향에 맞게 돌리기
                if (cur.dir == -1) {
                    wheels.set(cur.w, wheels.get(cur.w).substring(1) + wheels.get(cur.w).charAt(0));
                } else if (cur.dir == 1) {
                    wheels.set(cur.w, wheels.get(cur.w).charAt(7) + wheels.get(cur.w).substring(0, 7));
                }

우선 bfs를 위해 큐를 입력받고, 회전할 톱니와 방향을 넣어주고 첫 톱니의 visit을 true로 설정한다. 이제 bfs를 도는 데, 톱니를 먼저 돌리고 진행하도록 하자.

• 톱니가 반시계 방향으로 돌 경우, 톱니 상태의 입력이 시계방향으로 진행되었으므로 left shift, 문자열의 맨 앞을 맨 두뒤로 보낸다.
• 톱니가 시계 방향으로 돌 경우, 톱니 상태의 입력이 시계방향으로 진행되었으므로 right shift, 문자열의 맨 뒤 문자를 맨 앞으로 보낸다.

                //왼쪽 톱니바퀴
                if (cur.w - 1 > 0 && !visit[cur.w - 1]) {
                    visit[cur.w - 1] = true;
                    //왼쪽 바퀴의 9시 방향 vs 현재 바퀴의 3시 방향 비교 -> 다르면 다른 방향으로 이동, 같으면 움직이지 않음
                    if (wheels.get(cur.w - 1).charAt(2) != wheels.get(cur.w).charAt(6 + cur.dir)) {
                        qu.offer(new Pair(cur.w - 1, -cur.dir));
                    } else {
                        qu.offer(new Pair(cur.w - 1, 0));
                    }
                }

                //오른쪽 톱니바퀴
                if (cur.w + 1 <= 4 && !visit[cur.w + 1]) {
                    visit[cur.w + 1] = true;
                    if (wheels.get(cur.w).charAt(2 + cur.dir) != wheels.get(cur.w + 1).charAt(6)) {
                        qu.offer(new Pair(cur.w + 1, -cur.dir));
                    } else {
                        qu.offer(new Pair(cur.w + 1, 0));
                    }
                }

이제 인접 톱니바퀴에 대해 보도록 하자. 해당 톱니바퀴가 존재하고, 아직 방문을 하지 않았다면 visit을 true로 바꾼다. 

톱니의 입력은 12시 방향에서 시작하여 시계 방향으로 주어졌으므로, 3시 방향 톱니의 인덱스는 2, 9시 방향 톱니의 인덱스는 6이다. 또, 해당 풀이에서는 bfs 시 현재 톱니를 먼저 돌리고 시작했으므로 현재 톱니의 비교에서는 dir(돌린 방향)을 더해주어야 한다. 시계 방향이므로 1이므로 +1, 반시계 방향이므로 -1을 해주어 다음 톱니와 비교한다. 

• 톱니의 극이 같을 경우, 다음 톱니와 그 이후의 톱니는 돌아가지 않으므로 dir을 0으로 저장해준다.
• 톱니의 극이 다를 경우, 현재 톱니의 반대 방향으로 돌아야 하므로 -를 붙여준다.

        int ans = 0;

        for (int i = 1; i <= 4; i++) {
            ans += (int) ((wheels.get(i).charAt(0) - '0') * Math.pow(2, i - 1));
        }

        System.out.println(ans);

점수 계산 부분이다. 점수는 12시 방향의 톱니가 S일 경우 i번 톱니는 2^(i-1)로 연산하고, S인 톱니는 1로 입력이 되었으므로 맞추어 계산 및 출력해준다.