[ 백준 ] 14891 톱니바퀴

📌 Problem

8개의 톱니를 가지는 4개의 톱니바퀴가 일렬로 연결되어 있다. 각각의 톱니는 1 또는 0인 상태이며 1은 S극 0은 N극이다. 하나의 톱니바퀴를 돌렸을 때 이웃한 톱니바퀴와 연결된 톱니가 서로 다른 극이면 이웃한 톱니바퀴는 반대 방향으로 회전한다. 톱니바퀴들을 K번 회전시킨 후 톱니바퀴의 윗톱니을 기준으로 점수를 매긴다. 윗톱니가 N극이면 0점이고 S극이면 2를 톱니 번호 - 1만큼 곱한 점수이다.(1, 2, 3, 4번의 S극 점수는 각각 1, 2, 4, 8 점이다.)

위의 상태를 기준으로 점수를 매기면 1 + 0 + 4 + 0 = 5 점이다.

📌 Solution

먼저 각각의 톱니바퀴를 나타내는 Gear 클래스와 필요한 enum을 정의한다. G번 톱니바퀴를 회전시키면 회전 이전에 양옆 톱니바퀴들을 DFS으로 탐색하면서 맞물린 톱니가 다른 극이면 이웃하는 톱니바퀴를 회전시킨다. 자세한 내용은 코드로 설명한다.

📌 Code

// 1번부터 4번까지의 톱니바퀴를 저장하는 Map 자료구조
Map<Integer, Gear> gears = new HashMap<>();

// 각각의 톱니바퀴를 생성한다.
for (int gno = 1; gno <= 4; gno++) {
    int[] state = Arrays.stream(reader.readLine().split("")).mapToInt(Integer::parseInt).toArray();
    Gear gear = new Gear(state);
    gears.put(gno, gear);
}

// 이웃하는 톱니바퀴들을 맞물린다.
for (int gno = 1; gno <= 4; gno++) {
    Gear gear = gears.get(gno);
    gear.addGear(Direction.LEFT, gears.get(gno - 1));   // 왼쪽 톱니바퀴
    gear.addGear(Direction.RIGHT, gears.get(gno + 1));  // 오른쪽 톱니바퀴
}

// 톱니바퀴를 골라서 회전시킨다.
StringTokenizer tokenizer;
int rnum = Integer.parseInt(reader.readLine());
while (rnum-- > 0) {
    tokenizer = new StringTokenizer(reader.readLine());
    Gear gear = gears.get(Integer.parseInt(tokenizer.nextToken()));
    gear.rotate(Integer.parseInt(tokenizer.nextToken()) == 1 ? Rotation.CLOCKWISE : Rotation.COUNTER_CLOCKWISE);
}

// 점수를 계산한다.
int score = IntStream.rangeClosed(1, 4)
        .map(gno -> (int) (gears.get(gno).getTopState() * Math.pow(2, gno - 1))).sum();

class Gear {

    private int top = 0;
    private Gear left, right;

    private final int[] state;

    public Gear(int[] state) {
        this.state = state;
    }

    /**
     * 현재 톱니바퀴에 이웃하는 톱니바퀴를 끼워넣는다.
     * @param direction 끼워넣는 방향으로 왼쪽 혹은 오른쪽
     * @param gear 끼워넣고자하는 톱니바퀴
     */
    public void addGear(Direction direction, Gear gear) {
        if (direction == Direction.LEFT) left = gear;           // 왼쪽에 추가
        else if (direction == Direction.RIGHT) right = gear;    // 오른쪽에 추가
    }

    /**
     * 현재 톱니바퀴의 윗방향 톱니의 상태를 반환한다. 0이면 N극 1이면 S극이다.
     * @return 톱니의 상태 (0-N or 1-S)
     */
    public int getTopState() {
        return state[top];
    }

    /**
     * 톱니바퀴를 직접 회전시킨다.
     * @param rotation 회전시키는 방향
     */
    public void rotate(Rotation rotation) {
        // 왼쪽에 톱니가 있으며, 맞물린 톱니의 상태(극)가 다르면 왼쪽 톱니바퀴를 반대 방향으로 회전시킨다.
        if (left != null && isStickTogether(Direction.LEFT)) left.rotate(rotation.opposite(), Direction.LEFT);

        // 오른쪼에 톱니가 있으며, 맞물린 톱니의 상태(극)가 다르면 오른쪽 톱니바퀴를 반대 방향으로 회전시킨다.
        if (right != null && isStickTogether(Direction.RIGHT)) right.rotate(rotation.opposite(), Direction.RIGHT);

        // 현재 톱니바퀴를 회전시킨다.
        top = (top + (rotation == Rotation.CLOCKWISE ? 7 : 1)) % 8;
    }

    /**
     * 다른 톱니바퀴의 회전으로 인하여 회전시킨다.
     * @param rotation 회전시키는 방향
     * @param direction 회전이 진행되는 방향 (오른쪽 톱니바퀴의 회전으로 인한 회전이면 LEFT 반대면 RIGHT)
     */
    private void rotate(Rotation rotation, Direction direction) {
        // 왼쪽으로 회전이 진행되면서 왼쪽 톱니바퀴가 있고 맞물린 톱니의 상태(극)가 다르면 왼쪽 톱니바퀴를 회전시킨다.
        if (direction == Direction.LEFT && left != null && isStickTogether(direction))
            left.rotate(rotation.opposite(), direction);

        // 오른쪽으로 회전이 진행되면서 오른쪽 톱니바퀴가 있고 맞물린 톱니의 상태(극)가 다르면 오른쪽 톱니바퀴를 회전시킨다.
        if (direction == Direction.RIGHT && right != null && isStickTogether(direction))
            right.rotate(rotation.opposite(), direction);

        // 현재 톱니바퀴를 회전시킨다.
        top = (top + (rotation == Rotation.CLOCKWISE ? 7 : 1)) % 8;
    }

    /**
     * 이웃한 톱니바퀴와 맞물린 톱니가 다른지 확인한다.
     * @param direction 비교하고자하는 톱니바퀴의 위치
     * @return 서로 다른 극으로 맞물려 있으며 true를 반환한다.
     */
    private boolean isStickTogether(Direction direction) {
        return getState(direction) != (direction == Direction.LEFT ? left : right).getState(direction.opposite());
    }

    /**
     * 왼쪽 혹은 오른쪽 톱니의 상태를 반환한다.
     * @param direction 알고자하는 톱니의 위치
     * @return 톱니의 상태(극)을 반환한다.
     */
    private int getState(Direction direction) {
        if (direction == Direction.LEFT) return state[(top + 6) % 8];
        if (direction == Direction.RIGHT) return state[(top + 2) % 8];
        throw new RuntimeException("Should not reach here");
    }
}

enum Rotation {
    CLOCKWISE, COUNTER_CLOCKWISE;

    public Rotation opposite() {
        return this == CLOCKWISE ? COUNTER_CLOCKWISE : CLOCKWISE;
    }
}

enum Direction {
    LEFT, RIGHT;

    public Direction opposite() {
        return this == LEFT ? RIGHT : LEFT;
    }
}