[백준 14891] 톱니바퀴 - JAVA

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

접근방법

가장 먼저 원리를 파악했습니다.

• 왼쪽 톱니바퀴와 맞닿는 톱니는 6번 인덱스
• 오른쪽 톱니바퀴와 맞닿는 톱니는 2번 인덱스
• 회전 이전에 회전 가능성 파악하기

이렇게 생각했고 모든 톱니바퀴를 char[][]로 관리할 수 있었지만
비트마스킹을 사용하는 것이 효율적일 것이라 생각해 int[]를 사용했습니다.

이진수를 십진수로 변환하는 convertDecimal로 정수로 변환해 톱니의 상태를 저장하는 cogwheels 배열에 저장했습니다.

rotate와 getPoint 알고리즘 프로세스는 다음과 같습니다.

Step 1: 회전 대상 탐색 (BFS)

현재 회전시킨 톱니를 기준으로 좌우로 확산하며 어떤 톱니가 돌아가야 할지 찾습니다.

• visited 배열을 사용하여 중복 탐색을 방지
• XOR (^) 연산을 통해 두 톱니의 맞닿은 극이 서로 다른지 확인
• 회전해야 할 톱니 번호와 방향을 별도의 큐(rotate)에 저장

Step 2: 실제 회전 수행 (Bit Shift)

시계 방향과 반시계 방향 회전을 비트 연산으로 처리합니다.

• 시계 방향 d == 1 :
  비트를 왼쪽으로 밀기(<< 1)
  범위를 벗어난 비트는 다시 0번 자리로 순환

• 반시계 방향 d == -1:
  비트를 오른쪽으로 밀기(>> 1)
  0번 비트가 유실되지 않도록 처리

Step 3: 점수 계산

최종적으로 각 cogwheels[i]의 0번 비트(12시 방향)를 확인하여 문제 조건에 맞게 합산합니다.

후기

로직들은 잘 구현해서 문제는 풀었지만 아쉬운 점은 BFS로 풀지 않고 for문 순회로도 조건 판별로 회전해야할 톱니바퀴를 구할 수 있었을 것 같은데 두 개의 큐를 사용해 문제를 풀어 조금 아쉬웠습니다..

코드

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


public class Main {
    static StringTokenizer st;
    static int[] dx = {-1, 1};
    static int[] check = {64, 4};
    static int[] cogwheels = new int[4];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (int i = 0; i < 4; i++) {
            cogwheels[i] = convertToDecimal(br.readLine().toCharArray());
        }

        int K = Integer.parseInt(br.readLine());
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            rotate(n, d);
        }
        System.out.println(getPoint());
    }

    private static int getPoint() {
        int point = 0;
        if ((cogwheels[0] & 1) == 1) point += 1;
        if ((cogwheels[1] & 1) == 1) point += 2;
        if ((cogwheels[2] & 1) == 1) point += 4;
        if ((cogwheels[3] & 1) == 1) point += 8;

        return point;
    }

    private static void rotate(int n, int dir) {
        boolean[] visited = new boolean[4];
        visited[n-1] = true;

        ArrayDeque<int[]> q = new ArrayDeque<>();
        ArrayDeque<int[]> rotate = new ArrayDeque<>();

        q.offer(new int[]{n-1, dir});
        rotate.offer(new int[]{n-1, dir});

        while (!q.isEmpty()) {
            int[] cogwheel = q.poll();
            int x = cogwheel[0];
            int d = cogwheel[1];

            for (int i = 0; i < 2; i++) {
                int nx = x + dx[i];

                if (0 <= nx && nx < 4 && !visited[nx]) {
                    if ((((cogwheels[x] & check[i]) != 0) ^ ((cogwheels[nx] & check[(i + 1) % 2])) != 0)) {
                        q.offer(new int[] {nx, d == 1 ? -1 : 1});
                        rotate.offer(new int[] {nx, d == 1 ? -1 : 1});
                    }
                    visited[nx] = true;
                }
            }
        }


        while (!rotate.isEmpty()) {
            int[] tmp = rotate.poll();
            int x = tmp[0];
            int d = tmp[1];

            if (d == 1) {
                if ((cogwheels[x] & 128) != 0) {
                    cogwheels[x] <<= 1;
                    cogwheels[x] -= 255;
                }
                else {
                    cogwheels[x] <<= 1;
                }
            }
            else {
                if ((cogwheels[x] & 1) != 0) {
                    cogwheels[x] >>= 1;
                    cogwheels[x] += 128;
                }
                else {
                    cogwheels[x] >>= 1;
                }
            }
        }
    }

    private static int convertToDecimal(char[] arr) {
        int tmp = 0;

        for (int i = arr.length - 1; i >= 0; i--) {
            tmp <<= 1;
            if (arr[i] == '1') tmp += 1;
        }

        return tmp;
    }
}