[백준] 15662 : 톱니바퀴 (2) (JAVA)

문제

BOJ 15662 : 톱니바퀴 (2) - https://www.acmicpc.net/problem/15662

풀이

문제 : 회전시킬 톱니바퀴 번호와 방향이 주어진다. 해당 톱니바퀴를 회전시킨 후, 왼쪽과 오른쪽 (양 옆)의 톱니바퀴를 본다. 양 옆의 톱니의 극이 다르다면 (N극-S극) 그 톱니바퀴를 현재 톱니바퀴를 회전시킨 방향의 반대 방향으로 회전시킨다.

재귀로 풀이했다. 현재 톱니바퀴를 회전시킨 후 양 옆의 톱니바퀴도 회전시키는데, 조건은 다음과 같다.

1. 왼쪽 혹은 오른쪽에 톱니바퀴가 존재하는지
2. 이전에 회전시키지 않은 톱니바퀴인지
3. 인접한 톱니가 반대 극인지

위 조건을 모두 만족한다면, 재귀적으로 함수를 호출한다.

rotate를 먼저 진행하기 때문에, 인접한 톱니의 극을 확인할 땐

• 왼쪽 톱니바퀴 : 왼쪽 톱니바퀴의 2번 바퀴와 현재 톱니바퀴의 6+direction(시계방향일 경우 7번, 반시계 방향일 경우 5번)번 바퀴를 확인한다.
• 오른쪽 톱니바퀴 : 오른쪽 톱니바퀴의 6번 바퀴와 현재 톱니바퀴의 2+direction(시계방향일 경우 3번, 반시계 방향일 경우 1번)번 바퀴를 확인한다.

rotate 작업은 방향을 나누어 시계방향일 경우/반시계방향일 경우 를 if~else문으로 나누어 구현했다. 예를 들어 반시계 방향으로 회전할 경우, 0번째 톱니 극을 저장해 놓은 뒤, for문을 활용해서 0번 바퀴에 1번 바퀴 극을 저장, 1번 바퀴에 2번 바퀴 극을 저장 ... 이후 7번 바퀴에 맨 처음에 저장해 둔 0번 바퀴 극을 저장하는 방법으로 rotate했다.

코드

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

public class Main {
    static int n;
    static boolean[] visited;
    static int[][] wheels;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        wheels = new int[n+1][8];
        for (int i = 1; i <= n; i++) {
            String tmp = br.readLine();
            for (int j = 0; j < 8; j++) {
                wheels[i][j] = Integer.parseInt(String.valueOf(tmp.charAt(j)));
            }
        }

        int tk = Integer.parseInt(br.readLine());
        for (int i = 0; i < tk; i++) {
            String[] tmp = br.readLine().split(" ");
            int wheel_num = Integer.parseInt(tmp[0]);
            int direction = Integer.parseInt(tmp[1]);

            visited = new boolean[n+1];
            compute(wheel_num, direction);
        }


        // print result
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (wheels[i][0] == 1) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }

    public static void compute(int wheel_num, int direction) {

        visited[wheel_num] = true;
        rotate(wheel_num, direction);

        if (wheel_num - 1 >= 1 && !visited[wheel_num-1] && wheels[wheel_num - 1][2] != wheels[wheel_num][6+direction]) {
            compute(wheel_num - 1, direction * -1);
        }
        if (wheel_num + 1 <= n && !visited[wheel_num + 1] && wheels[wheel_num + 1][6] != wheels[wheel_num][2+direction]) {
            compute(wheel_num + 1, direction * -1);
        }

    }

    public static void rotate(int wheel_num, int direction) {
        if (direction == 1) { // cw
            int tmp = wheels[wheel_num][7];
            for (int i = 7; i >= 1; i--) {
                wheels[wheel_num][i] = wheels[wheel_num][i-1];
            }
            wheels[wheel_num][0] = tmp;
        }else{ // ccw
            int tmp = wheels[wheel_num][0];
            for (int i = 0; i < 7; i++) {
                wheels[wheel_num][i] = wheels[wheel_num][i+1];
            }
            wheels[wheel_num][7] = tmp;
        }
    }
}

정리

✔ 알고리즘 분류 - 구현, 시뮬레이션
✔ 난이도 - ⚪ Silver 1

🤦‍♀️ 오늘의 메모

• 쪼오끔 귀찮은 문제지만 생각을 잘 하면 충분히 풀 수 있었던 문제다. 그림이 나오고 설명이 길어서 살짝 쫄았는데 그럴 필요 없음! 인접한 톱니바퀴를 어떻게 회전시킬까에 대한 생각을 잘 해야했던 문제였다.

참고 사이트

딱히 없음