백준 14891번 톱니바퀴 :: 마이구미

이 글은 백준 알고리즘 문제 14891번 "톱니바퀴" 를 풀이한다.

2017 삼성 SW 역량 테스트 기출 문제이다.

시뮬레이션을 통한 하드코딩으로 풀 수도 있다.

본인의 접근 방법은 덱(dequeue) 과 같은 개념과 재귀를 활용해 문제를 해결한다.

문제 링크 - https://www.acmicpc.net/problem/14891

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

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

다소 문제의 설명에서 많은 그림과 많은 글들이 있어, 복잡해보인다.

문제는 그렇게 복잡하지 않고, 이해하기도 어렵지 않다.

하지만 본인은 문제를 잘못 이해해서 꽤 오래 걸렸다.

문제를 통해 알 수 있는 정보는 다음과 같다.

1. 톱니바퀴는 총 4개가 존재한다.
2. 각 톱니바퀴의 톱니는 총 8개가 존재한다.
3. 서로 맞닿은 극의 톱니는 2번과 6번이다.
4. 서로 맞닿은 극이 다르면 회전시키고 그렇지 않다면, 그대로 유지한다.
5. 톱니바퀴의 인접한 톱니바퀴의 인접한 톱니바퀴도 고려해야한다.
6. 하나의 톱니바퀴를 기준으로 인접한 톱니바퀴는 기준 톱니바퀴의 반대방향으로 회전하게 된다.
7. 입력을 통해 첫 회전 시키는 톱니바퀴는 무조건 회전하는 것이고, 인접한 톱니바퀴가 회전여부를 판단하는 것이다.

본인은 양쪽 모두 맞닿은 극이 같을 경우, 그대로 유지해버렸다.

즉, 6번을 이해하지 못해 오래 걸렸다.

다시 말하자면, 주어지는 입력(회전하는 톱니바퀴 번호) 에 대한 톱니바퀴는 무조건 회전한다.

5번의 경우는 톱니바퀴들은 체인처럼 연결된다고 볼 수 있다.

즉, 4, 3, 2, 1 번 톱니바퀴 모두 회전할 수 있다.

4, 3, 2 번 톱니바퀴만 회전할 수 있다.

4, 3 번 톱니바퀴만 회전할 수 있다.

4 번 톱니바퀴만 회전할 수 있다.

결론적으로 문제를 통해 얻을 수 있는 정보를 가지고 시뮬레이션을 통해 그대로 구현하면 된다.

구현에 있어, 재귀와 덱을 사용하면 깔끔한 코드를 작성할 수 있다.

인접한 톱니바퀴는 계속 이어질 수도 있기 때문에 왼쪽과 오른쪽을 나누어 재귀적으로 해결한다.

회전은 반시계 방향일 경우 맨 앞의 요소를 맨 뒤로 보내면 되고, 시계 방향일 경우 맨 뒤의 요소를 맨 앞으로 보내면 된다.

이와 같은 개념은 덱을 나타낼 수 있다.

Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/dequeue/14891.java

static LinkedList<Integer>[] list = (LinkedList<Integer>[]) new LinkedList[5];
 
private void solve() {
    for (int i = 1; i <= 4; i++) {
        list[i] = new LinkedList<Integer>();
        String input = sc.readLine();
        for (String s : input.split("")) {
            int n = Integer.parseInt(s);
            list[i].add(n);
        }
    }
 
    int k = sc.nextInt();
    while (k-- > 0) {
        int n = sc.nextInt();
        int d = sc.nextInt();
 
        left(n - 1, -d);
        right(n + 1, -d);
        rotate(n, d);
    }
 
    int ans = 0;
    for (int i = 0; i < 4; i++) {
        if (list[i + 1].get(0) == 1) {
            ans += (int) Math.pow(2, i);
        }
    }
    System.out.println(ans);
}
 
public static boolean check(int a, int b) {
    if (a > b) {
        // left
        if (list[a].get(6) == list[b].get(2)) {
            return false;
        } else {
            return true;
        }
    } else {
        if (list[a].get(2) == list[b].get(6)) {
            return false;
        } else {
            return true;
        }
    }
}
 
public static void rotate(int n, int direction) {
    if (direction == 1) {
        list[n].addFirst(list[n].pollLast());
    } else {
        list[n].addLast(list[n].pollFirst());
    }
}
 
public static void left(int n, int direction) {
    if (!(1 <= n && n <= 4))
        return;
 
    if (check(n, n + 1)) {
        left(n - 1, -direction);
        rotate(n, direction);
    }
}
 
public static void right(int n, int direction) {
    if (!(1 <= n && n <= 4))
        return;
 
    if (check(n, n - 1)) {
        right(n + 1, -direction);
        rotate(n, direction);
    }
}