백준 14891번 : 톱니바퀴 java

이 문제는 문제에서 주어진 조건에 따라서 문제를 해결할 수 있는 알고리즘을 구현하는 문제입니다.

이 문제에서 주어진 조건에 대해서 설명해드리겠습니다.

위의 그림을 보시면 2번 톱니바퀴를 시계방향으로 굴린다고 가정했을 때 1번 톱니바퀴는 2번 톱니바퀴와 맞닿은 톱니가 서로 반대의 극을 가지고 있기 때문에 2번 톱니바퀴의 반대 방향인 반시계 방향으로 돌아가게 됩니다.

그리고 3번 톱니바퀴는 2번 톱니바퀴와 맞닿은 부분이 같은 극을 가지고 있기 때문에 돌아가지 않습니다.

이 알고리즘을 기반으로 코드를 구현해보도록 하였습니다.

---

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

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

        List<List<Integer>> LL = new ArrayList<>();
        for(int i = 0; i<4; i++){
            String[] input = br.readLine().split("");
            LL.add(new LinkedList<>());

            for(int j = 0; j<8; j++)
                LL.get(i).add(Integer.parseInt(input[j]));
        }

        int K = Integer.parseInt(br.readLine());

        while(K-->0){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int num = Integer.parseInt(st.nextToken()) -1;
            int dir = Integer.parseInt(st.nextToken());

            Queue<Node> q = new LinkedList<>();
            q.offer(new Node(num, dir));
            boolean[] visited = new boolean[4];
            visited[num] = true;

            while(!q.isEmpty()){
                Node a = q.poll();

                int right = a.num + 1;
                int left = a.num - 1;
                int nextDir = a.dir == -1 ? 1 : -1;

                if(right<4 && !visited[right]){
                    if(LL.get(a.num).get(2) != LL.get(right).get(6)) {
                        q.offer(new Node(right, nextDir));
                        visited[right] = true;
                    }
                }

                if(left>=0 && !visited[left]){
                    if(LL.get(a.num).get(6) != LL.get(left).get(2)){
                        q.offer(new Node(left, nextDir));
                        visited[left] = true;
                    }
                }

                // 시계 방향 회전이니 마지막 수를 빼와서 처음에 삽입
                if(a.dir == 1)
                    LL.get(a.num).add(0, LL.get(a.num).remove(7));
                // 반시계 방향 회전이니 처음 수를 빼서 마지막에 삽입
                else
                    LL.get(a.num).add(LL.get(a.num).remove(0));
            }
        }
        int sum = 0;
        for(int i = 0; i<4; i++){
            if(LL.get(i).get(0) == 1)
                sum += Math.pow(2, i);
        }

        System.out.println(sum);
    }
}
class Node{
    int num, dir;

    Node(int num, int dir){
        this.num = num;
        this.dir = dir;
    }
}

위 코드는 List<List<Integer>> 리스트를 이용하여 각각의 톱니바퀴의 상태를 담았습니다.

그리고 12시 방향이 0번 인덱스이고 시계방향으로 각각의 인덱스에 자료가 들어갔으니 오른쪽 톱니바퀴와 닿는 부분은
2이고 왼쪽 톱니바퀴와 닿는 부분의 인덱스는 6입니다.

이를 그림으로 나타내면 위와 같습니다.

맞닿은 부분의 극이 다르다면 주변의 톱니바퀴를 회전시키고 이를 큐에 추가하여 그 옆의 톱니바퀴도 확인하게
만들었습니다.