[Algorithm] SW 기출문제 - 톱니바퀴(14891) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

 

이번 포스팅은 백준 SW 기출문제 톱니바퀴 자바 풀이를 진행하고자 합니다.!

 

문제 출처: https://www.acmicpc.net/problem/14891

14891번: 톱니바퀴

 

 

1. 풀이 소스:

 

import java.util.*;
import java.io.*;

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Gear gear = new Gear();
        for (int i = 0; i < 4; i++) {
            String gearStatus = br.readLine();
            for (int j = 0; j < 8; j++) {
                gear.addStatus(i, j, gearStatus.charAt(j));
            }
        }

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

        gear.run();

        System.out.println(gear.getScore());
    }
}

class Gear {

    int[][] map = new int[4][8];
    Queue<Rotate> rotates = new ArrayDeque<>();
    Gear(){}

    void addStatus(int row, int col, char status) {
        map[row][col] = Character.getNumericValue(status);
    }

    void setRotate(int number, int dir) {
        rotates.add(new Rotate(number - 1, dir)); // 번호가 1부터인데 인덱스는 0부터 설정
    }

    void run() { // 극 N = 0, S = 1  dir:  시계 = 1, 반시계 = -1
        while (!rotates.isEmpty()) {
            Rotate rt = rotates.poll();
            int number = rt.number;
            int dir = rt.dir;

            int two = map[number][2];
            int six = map[number][6];

            rotate(number, dir);

            if (number == 0) dfs(number + 1, two, dir, false); // 오른쪽으로 이동하면서 회전
            else if (number == 3) dfs(number - 1, six, dir, true); // 왼쪽으로 이동
            else { // 1, 2는 양쪽 방향으로 진행
                dfs(number + 1, two, dir, false);
                dfs(number - 1, six, dir, true);
            }
        }
    }

    void rotate(int number, int dir) { // 극 N = 0, S = 1  dir:  시계 = 1, 반시계 = -1
        int[] tmp = map[number].clone(); // 복사 배열
        if (dir == 1) { // 시계
            // 이전항이 자신의 항
            System.arraycopy(tmp, 0, map[number], 1, 7);
            map[number][0] = tmp[7];
        } else { // 반시계
            // 다음 항이 자신의 항
            System.arraycopy(tmp, 1, map[number], 0, 7);
            map[number][7] = tmp[0];
        }
    }

    // 극이 달라야 회전
    void dfs(int nowNum, int prePole, int preDir, boolean toLeft) {
        if (nowNum == -1 || nowNum == 4) return;
        int nowDir = preDir == 1 ? -1 : 1; // 역방향

        int two = map[nowNum][2]; // 회전 시키기 전 고정 값
        int six = map[nowNum][6];

        if (toLeft) { // 영향 주는 곳은 6, 받는 곳은 2
            if (prePole == two) return; // 극이 같기에 더 이상 진행 x

            rotate(nowNum, nowDir); // 극이 다르다면 방향과 다르게 진행 회전
            dfs(nowNum - 1, six, nowDir, true); // 번호를 낮춰서, 다음 재귀

        } else { // 오른쪽으로 이동시 영향 주는 곳은 2, 받는 곳 6
            if (prePole == six) return; // 극이 같기에 더 이상 진행 x

            rotate(nowNum, nowDir);
            dfs(nowNum + 1, two, nowDir, false);
        }
    }

    int getScore() {  // 극 N = 0, S = 1  dir:  시계 = 1, 반시계 = -1
        int score = 0;

        score += map[0][0] == 0 ? 0 : 1;
        score += map[1][0] == 0 ? 0 : 2;
        score += map[2][0] == 0 ? 0 : 4;
        score += map[3][0] == 0 ? 0 : 8;

        return score;
    }

    class Rotate {
        int number;
        int dir;

        Rotate (int number, int dir) {
            this.number = number;
            this.dir = dir;
        }
    }
}

 

 

2.  풀이 중점 사항

 

해당 문제는 재귀를 활용하여 톱니바퀴 회전 가능 여부를 확인하고 회전하는 방법으로 문제를 해결할 수 있습니다.

0, 3의 인덱스를 가진 톱니바퀴(문제 1번,  4번 톱니바퀴)는 각 단방향으로만 영향을 줄 수 있습니다.

•  인덱스 0번 톱니바퀴는 오른쪽 톱니바퀴에 영향
•  인덱스 3번 톱니바퀴는 왼쪽 톱니바퀴에 영향
•  인덱스 1번, 인덱스 2번 톱니바퀴는 왼쪽, 오른쪽 각각 모두 영향을 줍니다.

 

이 영향성을 가지고 문제 해결 전략을 세울 수 있습니다.

• 먼저, 회전할 톱니바퀴 인덱스와 방향을 큐에 넣습니다.
• 큐가 빌 때 까지 회전을 진행합니다.
• 큐에서 나온 톱니바퀴는 무조건 회전을 1회 진행합니다.
• 큐에서 나온 번호를 토대로 위에서 정의한 방법으로 재귀를 진행합니다.
• 중요한 점은 톱니바퀴에 영향을 주는 극은 회전 이전의 극입니다. 즉, 회전 이전에 영향을 주는 2번 인덱스와 6번 인덱스의 번호를 가진 톱니바퀴의 칸을 미리 변수로 설정한 후, 회전 이후의 값이 영향을 주지 않도록 합니다.
• 만약 왼쪽으로 톱니바퀴에 영향을 주는 재귀라면 이전 톱니바퀴의 6번 칸이 현재 톱니바퀴의 2번과 같은지 여부를 판단하고 회전을 시행합니다.
• 만약 오른쪽 톱니바퀴에 영향을 주는 재귀라면 이전 톱니바퀴의 2번 칸이 현재 톱니바퀴의 6번과 같은지 여부를 판단하고 회전을 시행합니다.
• 만약 인덱스가 -1 혹은 인덱스 4라면 재귀를 멈추고, 이전 톱니바퀴의 칸의 극과 현재 톱니바퀴의 칸 극이 같다면 재귀를 종료합니다.

 

 

rotate 메서드

 

void rotate(int number, int dir) { // 극 N = 0, S = 1  dir:  시계 = 1, 반시계 = -1
    int[] tmp = map[number].clone(); // 복사 배열
    if (dir == 1) { // 시계
        // 이전항이 자신의 항
        System.arraycopy(tmp, 0, map[number], 1, 7);
        map[number][0] = tmp[7];
    } else { // 반시계
        // 다음 항이 자신의 항
        System.arraycopy(tmp, 1, map[number], 0, 7);
        map[number][7] = tmp[0];
    }
}

 

회전할 때 중요한 점은 시계와 반시계 방향으로 회전할 때 이전 항 혹은 다음 항을 기억할 tmp 배열을 생성해야 합니다.

자바에서는 System.arraycopy() 메서드로 해결할 수 있습니다.

  

System.arraycopy(복사할 배열, 복사할 배열의 시작점, 복사될 배열, 복사될 배열의 시작점, 총 복사할 개수);

 

시계 방향의 경우 -> 방향이기 때문에 복사할 배열의 시작점은 0이 됩니다.

복사될 배열인 map[number]는 시작점이 1입니다.

즉, 0번의 인덱스 값이 1에 복사된다는 의미이므로 시계 방향 회전을 수행할 수 있고 복사할 개수가 7이므로

map[number][0]은 tmp[7]로 원형 시계를 설정할 수 있습니다.

 

 

dfs 메서드

 

 void dfs(int nowNum, int prePole, int preDir, boolean toLeft) {
    if (nowNum == -1 || nowNum == 4) return;
    int nowDir = preDir == 1 ? -1 : 1; // 역방향

    int two = map[nowNum][2]; // 회전 시키기 전 고정 값
    int six = map[nowNum][6];

    if (toLeft) { // 영향 주는 곳은 6, 받는 곳은 2
        if (prePole == two) return; // 극이 같기에 더 이상 진행 x

        rotate(nowNum, nowDir); // 극이 다르다면 방향과 다르게 진행 회전
        dfs(nowNum - 1, six, nowDir, true); // 번호를 낮춰서, 다음 재귀

    } else { // 오른쪽으로 이동시 영향 주는 곳은 2, 받는 곳 6
        if (prePole == six) return; // 극이 같기에 더 이상 진행 x

        rotate(nowNum, nowDir);
        dfs(nowNum + 1, two, nowDir, false);
    }
}

 

각 톱니바퀴는 회전 이전의 값을 반드시 가지고 있어야 합니다. 즉, 영향을 줄 수 있는 톱니바퀴가 회전한 결과를 넘겨준다면 문제에 위배되게 됩니다.

 

이를 구현하기 위해 two, six로 회전 이전의 값을 저장했습니다.

만약, toLeft == true로 왼쪽 방향으로 이동하는 것이라고 가정한다면,

 

먼저 prePole == two의 극을 비교합니다. prePole은 맞대는 이전 톱니바퀴의 6번 칸의 극을 의미합니다 (왼쪽으로 이동하므로 현재 톱니바퀴의 이전 톱니바퀴는 오른쪽에 위치합니다.)

 

두 극이 다르다면, 회전을 수행합니다.

 

왼쪽 방향성을 그대로 유지하면서, 톱니바퀴 번호는 하나 낮추고, 회전 이전의 값인 map[number][6], 현재 회전한 방향을 파라미터로 설정하여 재귀를 진행합니다.

 

이렇게 함으로써 다음 재귀가 실행될 때는, prePole을 받았을 때, 회전 이전의 값을 받을 수 있습니다.

 

 

이상으로 톱니바퀴 자바 풀이를 마치도록 하겠습니다. 감사합니다.!