[백준] 14891번 / Java / 톱니바퀴 - 구현, 시뮬레이션, 재귀풀이

문제 - (https://www.acmicpc.net/problem/14891)

시뮬레이션 문제... 솔직히 시간 좀 많이 잡아먹는다

실버 1 수준의 문제인데도 푸는데 1시간 정도 걸렸다

구현 문제는 특히 헷갈리는 부분 때문에 실수가 잦아 조심해야 한다

 

우선 꼭 짚고 넘어가야 할 것들만 언급하고 주의할 점과 내가 실수한 것을 쓰고 마치겠다

 

👀짚고 넘어가야 할 부분1 - 톱니바퀴 회전시키기

static String clockRotate(String state, int dir) {
        if (dir == 1) { // 시계 방향
            return state.charAt(state.length() - 1) + state.substring(0, state.length() - 1);
        } else { // 반시계 방향
            return state.substring(1) + state.charAt(0);
        }
}

다른 사람 풀이를 보니까 배열로 만들어서 푸셨던데.. 난 그냥 문자열 떼서 붙이는 방법 사용했다.

시계방 향일 경우, 문자열의 마지막 글자를 떼어내서 앞에 붙임

반시계 방향일 경우, 문자열 첫 번째 글자를 떼어내서 마지막에 붙임

 

👀짚고 넘어가야 할 부분2 - 재귀 구현하기

톱니바퀴 하나를 이동시키게 되면 그 톱니바퀴와 연결된 왼쪽, 오른쪽 톱니바퀴에도 영향이 미친다. 영향이 미친 톱니바퀴가 회전하게 되면 그 옆의 톱니바퀴에도 영향을 미친다. 이런 연쇄적인 현상 때문에 재귀로 구현해야겠다는 생각을 했다. (하지만 톱니가 4개밖에 없으니 굳이 재귀는 아니어도 상관없을 듯)

내가 구현한 재귀 구조는 회전해야 하는 톱니바퀴들 중 가장 끝에 있는 것부터 회전시키는 방식이다.

void rotate(int idx, int dir, boolean l, boolean rr)에서 boolean값의 의미는,

만약에 왼쪽 톱니바퀴가 움직이게 된다면 왼쪽 톱니바퀴로 재귀 진입을 하게 되는데, 그 상태에서는 계속해서 왼쪽에만 영향을 끼치므로 오른쪽 톱니바퀴에는 관여하지 않게 하기 위한 장치이다.

---

📌주의할 점

• 처음 움직일 톱니바퀴는 왼쪽 톱니바퀴와 오른쪽 톱니바퀴 모두 영향을 끼친다.
• 톱니바퀴 1과 톱니바퀴 4는 각각 왼쪽 톱니바퀴, 오른쪽 톱니바퀴가 없다.
• 12방향이 1일 때 톱니바퀴별로 점수가 부여되므로 score배열에 1,2,4,8을 넣어 점수 합계를 쉽게 했다.

---

😅실수

• 재귀 내부에서 계산 작업이 이루어진다면 진입할 때 계산을 하는 게 맞을지에 대해 고민은 꼭 해봐야 한다.
  아래 코드의 /**/ 주석에 설명이 적혀있음

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 실버1 - 1시간
public class Gear {
    static String[] gears = new String[5];
    static int[] score = {0, 1, 2, 4, 8};
    static int k;

    static void rotate(int idx, int dir, boolean l, boolean r) {
        // 현재 기어의 왼쪽, 오른쪽 기어 idx
        int leftIdx = idx - 1;
        int rightIdx = idx + 1;

        // 현재 기어와 왼쪽 기어 비교
        if (l && leftIdx >= 1 && gears[idx].charAt(6) != gears[leftIdx].charAt(2)) {
            // 다르면 왼쪽 기어 반대방향으로 회전
            rotate(leftIdx, -dir, true, false);
            /* 왼쪽 톱니바퀴에 진입한 후에 그 톱니바퀴가 현재 톱니바퀴가 되어 회전하는 작업을 "ㄱ"줄에서
            * 진행하므로 여기서 회전작업을 해버리면 중복 회전시키게 된다. */
//            gears[leftIdx] = clockRotate(gears[leftIdx], -dir);
        }

        if (r && rightIdx <= 4 && gears[idx].charAt(2) != gears[rightIdx].charAt(6)) {
            // 다르면 오른쪽 기어 반대방향으로 회전
            rotate(rightIdx, -dir, false, true);
//            gears[rightIdx] = clockRotate(gears[rightIdx], -dir);
        }

        // 현재 기어 회전시키기
        /* ㄱ */gears[idx] = clockRotate(gears[idx], dir);
    }

    static String clockRotate(String state, int dir) {
        if (dir == 1) { // 시계 방향
            return state.charAt(state.length() - 1) + state.substring(0, state.length() - 1);
        } else { // 반시계 방향
            return state.substring(1) + state.charAt(0);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        gears[1] = br.readLine();
        gears[2] = br.readLine();
        gears[3] = br.readLine();
        gears[4] = br.readLine();

        k = Integer.parseInt(br.readLine());

        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            rotate(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), true, true);
        }

        int answer = 0;

        for (int i = 1; i <= 4; i++) {
            if (gears[i].charAt(0) == '1') {
                // S극이면 점수가 있음
                answer += score[i];
            }
        }

        System.out.println(answer);
    }
}