[백준] 14891 톱니바퀴 - 자바

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

14891번: 톱니바퀴

문제 풀이

이 문제를 풀 때 가장 중요한 것은 중앙 톱니바퀴를 기준으로 좌측/우측의 극이 다를 경우 회전을 하게 되는데 이때 중앙 톱니바퀴를 회전하기 전에 좌측/우측의 극을 먼저 확인 후에 회전시켜야 한다는 것이다.

또한 극이 다를 경우 좌측/우측의 톱니바퀴가 회전하게 되는데 이 톱니바퀴에 의해 또 다른 좌/우측의 톱니바퀴가 회전할 수 있다. 따라서 재귀를 통해 좌/우측의 극이 같을 때까지 반복해주면 된다.

 

톱니바퀴는 배열로 구현할 경우 인덱스 관리가 복잡해져서 회전을 고려하여 List로 구현

시계방향 회전 [0,1,2,3,4,5] -> [5,1,2,3,4] -> 인덱스 0부터 4까지 제거 후 다시 삽입
반시계방향 회전 [0,1,2,3,4,5] -> [1,2,3,4,5,0] -> 인덱스 0을 제거 후 다시 삽입

 

구현문제는 실수가 많은 카테고리로 실수를 방지하기 위해 상수값을 자주 사용하는 편이다

static final int MIN_IDX = 0; // 톱니바퀴 최소 idx
static final int MAX_IDX = 3; // 톱니바퀴 최대 idx
static final int LEFT = 6; // 톱니바퀴가 겹쳐질 때 왼쪽값
static final int RIGHT = 2; // 톱니바퀴가 겹쳐질 때 오른쪽값
static final int S = 1; // S극

 

//init
for (int i = 0; i < 4; i++) {
    String line = br.readLine();
    cogwheels[i] = new ArrayList<>();
    for (int j = 0; j < 8; j++) {
        cogwheels[i].add(line.charAt(j) - '0');
    }
}

 

회전 횟수만큼 재귀 메소드 실행 left와 right를 분리

int rotateCnt = Integer.parseInt(br.readLine());
for (int i = 0; i < rotateCnt; i++) {
    st = new StringTokenizer(br.readLine());
    int idx = Integer.parseInt(st.nextToken()) - 1;
    int dir = Integer.parseInt(st.nextToken());

    turnLeft(idx, dir); // 좌측 연쇄
    turnRight(idx, dir); // 우측 연쇄
    rotate(idx, dir);
}

 

앞서 말했듯이 회전을 하기 전에 좌측의 톱니바퀴가 회전을 해야하는지를 체크하기 위해 turnLeft() 메소드를 먼저 실행

static void turnLeft(int now, int dir) {
    int leftIdx = now - 1;
    if (leftIdx < MIN_IDX) {
        return;
    }

    // 좌측 톱니바퀴와 겹치는 부분의 극이 다르다면 좌측 톱니바퀴로 재귀
    if (cogwheels[now].get(LEFT) != cogwheels[leftIdx].get(RIGHT)) {
        turnLeft(leftIdx, -dir);
        rotate(leftIdx, -dir);
    }

}

 

톱니바퀴의 회전방향에 맞게 회전

static void rotate(int now, int dir) {
    // 1:시계, -1:반시계
    if (dir == 1) {
        for (int i = 0; i < 7; i++) {
            int remove = cogwheels[now].remove(0);
            cogwheels[now].add(remove);
        }
    }
    if (dir == -1) {
        int remove = cogwheels[now].remove(0);
        cogwheels[now].add(remove);
    }
}

 

 

 

 

코드

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static final int MIN_IDX = 0; // 톱니바퀴 최소 idx
    static final int MAX_IDX = 3; // 톱니바퀴 최대 idx
    static final int LEFT = 6; // 톱니바퀴가 겹쳐질 때 왼쪽값
    static final int RIGHT = 2; // 톱니바퀴가 겹쳐질 때 오른쪽값
    static final int S = 1; // S극
    static List<Integer>[] cogwheels = new ArrayList[4];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        //init
        for (int i = 0; i < 4; i++) {
            String line = br.readLine();
            cogwheels[i] = new ArrayList<>();
            for (int j = 0; j < 8; j++) {
                cogwheels[i].add(line.charAt(j) - '0');
            }
        }

        int rotateCnt = Integer.parseInt(br.readLine());
        for (int i = 0; i < rotateCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int idx = Integer.parseInt(st.nextToken()) - 1;
            int dir = Integer.parseInt(st.nextToken());

            turnLeft(idx, dir); // 좌측 연쇄
            turnRight(idx, dir); // 우측 연쇄
            rotate(idx, dir);
        }

        // 점수 계산
        int score = 0;
        for (int i = 0; i < 4; i++) {
            if (cogwheels[i].get(0) == S) {
                score += Math.pow(2, i);
            }
        }
        System.out.println(score);
    }

    static void turnLeft(int now, int dir) {
        int leftIdx = now - 1;
        if (leftIdx < MIN_IDX) {
            return;
        }

        // 좌측 톱니바퀴와 겹치는 부분의 극이 다르다면 좌측 톱니바퀴로 재귀
        if (cogwheels[now].get(LEFT) != cogwheels[leftIdx].get(RIGHT)) {
            turnLeft(leftIdx, -dir);
            rotate(leftIdx, -dir);
        }

    }

    private static void rotate(int now, int dir) {
        // 1:시계, -1:반시계
        if (dir == 1) {
            for (int i = 0; i < 7; i++) {
                int remove = cogwheels[now].remove(0);
                cogwheels[now].add(remove);
            }
        }
        if (dir == -1) {
            int remove = cogwheels[now].remove(0);
            cogwheels[now].add(remove);
        }
    }

    static void turnRight(int now, int dir) {
        int rightIdx = now + 1;
        if (rightIdx > MAX_IDX) {
            return;
        }

        // 좌측 톱니바퀴와 겹치는 부분의 극이 다르다면 좌측 톱니바퀴로 재귀
        if (cogwheels[now].get(RIGHT) != cogwheels[rightIdx].get(LEFT)) {
            turnRight(rightIdx, -dir);
            rotate(rightIdx, -dir);
        }
    }
}