[백준] 14891. 톱니바퀴 (Java)

시뮬레이션에 간단한 BFS가 추가된 문제

 

14891번: 톱니바퀴

풀이

톱니바퀴를 돌릴 때 인덱스 값만 조정해서 실제 톱니바퀴는 돌리지 않는다.

인덱스 값이 변하는 규칙은 톱니바퀴 방향에 -1을 곱한 값을 더해주는 것이다.

 

queue를 사용해서 현재 톱니바퀴 기준 양옆을 조사하면서 뻗어나간다.

 

톱니바퀴는 이동할 톱니바퀴를 모두 저장 후 마지막에 동시에 돌려야 하므로 별도의 큐로 관리했다.

 

마지막에 12시 위치의 인덱스 값을 계산해서 답을 구한다.

 

 

• int[][] cog: 톱니바퀴 정보
• int[][] idx: 톱니바퀴의 왼쪽, 오른쪽 맞닿아 있는 부분의 index 값 (final int LEFT = 0, RIGHT = 1 로 semantic하게 관리)
• int[][] order: 톱니바퀴 회전 정보

Logic

1. 입력이 이어진 String으로 주어져 있으므로 split("")을 사용하여 쪼개서 입력받는다. 이때 각 톱니바퀴의 LEFT, RIGHT index값도 초기화한다.
2. 각 톱니바퀴 회전마다 다음 변수를 만든다.
   • boolean[] visited: 톱니바퀴 방문 관리
   • Queue<Cog> q: 다음에 방문할 톱니바퀴 정보. BFS용
   • Queue<Cog> temp: 돌려야 할 톱니바퀴 정보
     왼쪽, 오른쪽을 살핀 후 극이 다르다면 q에 넣는다. 방문하지 않은 톱니바퀴에 대해선 temp에 넣는다.
   • temp에 들어있는 톱니바퀴에 대해 LEFT, RIGHT index값을 조작한다.
3. 12시 방향에 있는 인덱스를 구하고, 문제 조건에 따라 답을 구한다.

코드

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


public class Main {
    static final int LEFT = 0, RIGHT = 1;
    static int K;
    static int[][] cog = new int[5][10];
    static int[][] idx = new int[5][2];
    static int[][] order;

    public static void main(String[] args) throws IOException {
        input();
        solve();
        System.out.println(getAnswer());
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        for (int i = 1; i <= 4; i++) {
            String[] temp = br.readLine().split("");

            for (int j = 0; j < 8; j++)
                cog[i][j] = Integer.parseInt(temp[j]);

            idx[i][LEFT] = 6;
            idx[i][RIGHT] = 2;
        }

        K = Integer.parseInt(br.readLine());
        order = new int[K][2];
        for (int k = 0; k < K; k++) {
            st = new StringTokenizer(br.readLine());
            order[k][0] = Integer.parseInt(st.nextToken());
            order[k][1] = Integer.parseInt(st.nextToken());
        }
    }

    public static void solve() {
        for (int k = 0; k < K; k++) {
            Queue<Cog> q = new LinkedList<>();
            Queue<Cog> temp = new LinkedList<>();
            boolean[] visited = new boolean[5];

            q.offer(new Cog(order[k][0], order[k][1]));
            temp.offer(new Cog(order[k][0], order[k][1]));
            while(!q.isEmpty()) {
                int num = q.peek().num;
                int d = q.peek().d;
                q.poll();

                if (num < 1 || num > 4 || visited[num]) continue;
                visited[num] = true;

                if (num != 1 && cog[num][idx[num][LEFT]] != cog[num - 1][idx[num - 1][RIGHT]]) {
                    q.offer(new Cog(num - 1, -d));
                    if (!visited[num - 1]) temp.offer(new Cog(num - 1, -d));
                }

                if (num != 4 && cog[num][idx[num][RIGHT]] != cog[num + 1][idx[num + 1][LEFT]]) {
                    q.offer(new Cog(num + 1, -d));
                    if (!visited[num + 1]) temp.offer(new Cog(num + 1, -d));
                }
            }

            while(!temp.isEmpty()) {
                int num = temp.peek().num;
                int d = temp.peek().d;
                temp.poll();

                idx[num][LEFT] = (idx[num][LEFT] - d + 8) % 8;
                idx[num][RIGHT] = (idx[num][RIGHT] - d + 8) % 8;
            }
        }

    }

    public static int getAnswer() {
        int sum = 0;
        for (int i = 1; i <= 4; i++) {
            int noon = (idx[i][RIGHT] + 6) % 8;
            if (cog[i][noon] == 1) sum += (int)Math.pow(2, i - 1);
        }

        return sum;
    }

    static class Cog {
        int num;
        int d;

        public Cog(int num, int d) {
            this.num = num;
            this.d = d;
        }

    }
}

실행 결과