[백준 - 14891 JAVA] 톱니바퀴 : 재귀 사용

일단 문제가 너무 장황해서 보기 어려웠지만 하나씩 이해하고자 하니 괜찮았다. 

그러나 주어진 그림 예시에서는 하나가 움직이면 연쇄적으로 움직여야하는 상황에 대해 캐치하지 못하였어서 예시 4번에서 계속 원하는 값이 나오지 않았다. (이때까지는 재귀 생각 못함) 

그래서 질문 게시판을 보니 연쇄적으로 움직이는 상황도 생각해야한다고 하여 재귀로 풀기로 결심하였다.

 

고려사항

• 모든 경우의 수에 맞춰 if문을 작성했다가 너무 코드가 복잡해지고 생각 못한 조건에 대해 커버를 하지 못해 재귀로 변경
• 1 base가 아니라 0 base 라서 시작시 wheelNum - 1 로 진행 
• 방문했다는 visited를 사용해야만 문제가 해결 되었다. 
  • 해당 톱니바퀴를 돌리고자 했었다 라는 표시를 해둬야 연쇄적으로 돌아가야하는 재귀에서 돌아가지 말아야할 것이 돌지 않도록 함
• Arrays.copyOf 는 깊은 복사로, 배열을 인자로 넘겨 받았을때 해당 배열의 값을 수정하면 주소값으로 넘겨 받았기 때문에 원 배열의 값이 바껴버림. 고로 깊은 복사를 통해 임시 복사를 해놓고 원 배열을 바꾸도록 함  

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

public class Main {

    static boolean[][] wheels = new boolean[4][8];
    static boolean[] visited;

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

        for (int i = 0; i < 4; i++) {
            String s = br.readLine();
            char[] chars = s.toCharArray();
            for (int j = 0; j < chars.length; j++) {
                wheels[i][j] = chars[j] == '1';
            }
        }

        int k = Integer.parseInt(br.readLine());
        StringTokenizer tokenizer;
        for (int i = 0; i < k; i++) {

            tokenizer = new StringTokenizer(br.readLine());
            int wheelNum = Integer.parseInt(tokenizer.nextToken());
            boolean isForward = tokenizer.nextToken().equals("1");

            visited = new boolean[4];
            rotate(wheelNum - 1, isForward, wheels);

        }

        int point = 0;
        for (int j = 0; j < wheels.length; j++) {
            boolean[] wheel = wheels[j];
            if (wheel[0]) {
                point += (int) Math.pow(2, j);
            }
        }
        System.out.println(point);
    }

    static void rotate(int target, boolean isForward, boolean[][] wheels) {
        boolean[][] copyWheels = Arrays.copyOf(wheels, wheels.length);
        visited[target] = true;
        if (target < 3 && !visited[target + 1] && copyWheels[target][2] != copyWheels[target + 1][6]) {
            rotate(target + 1, !isForward, copyWheels);
        }
        if (target > 0 && !visited[target - 1] && copyWheels[target - 1][2] != copyWheels[target][6]) {
            rotate(target - 1, !isForward, copyWheels);
        }
        verifyDirection(target, isForward, copyWheels);
    }


    static void verifyDirection(int wheelNum, boolean isForward, boolean[][] copyWheels) {
        if (isForward) {
            forward(wheelNum, copyWheels);
        } else {
            reverse(wheelNum, copyWheels);
        }
    }


    static void forward(int wheelNum, boolean[][] copyWheels) {
        boolean[] wheel = wheels[wheelNum];
        boolean[] temp = copyWheels[wheelNum];
        for (int i = 0; i < wheel.length; i++) {
            wheel[(i + 1) % 8] = temp[i];
        }
    }

    static void reverse(int wheelNum, boolean[][] copyWheels) {
        boolean[] wheel = wheels[wheelNum];
        boolean[] temp = copyWheels[wheelNum];
        for (int i = 0; i < wheel.length; i++) {
            wheel[(i - 1) < 0 ? 7 : (i - 1)] = temp[i];
        }
    }

}

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