[백준] 14891번 톱니바퀴

생각

4개의 톱니바퀴가 있다. 그 중 한 개를 돌린다고 할 때 양 쪽에 있는 톱니바퀴들은 해당 톱니가 같은 톱니로 짝이 이루어져있으면 돌지 않고 다른 톱니로 짝이 이루어져있으면 돌게된다. 처음 톱니바퀴의 상태를 주고, K개의 회전 케이스를 주고 모든 회전을 마쳤을 때 각 톱니바퀴의 12시 방향의 숫자 합을 번호 순서대로 1,2,4,8을 곱한 값을 출력하여라.

비고 사항

삼성 SW 테스트 기출이라고 한다.

처음 생각

우선 톱니바퀴의 상태가 10101111 이런 형태로 주어져 있고, 톱니바퀴는 4개로 제한되어 있으므로 [4][8] 형태의 이차 배열로 입력을 받았다.

다음 생각

톱니바퀴의 회전 케이스가 K개 만큼 들어온다. 전부 동시에 회전하는것이 아닌 각각의 회전 케이스이므로 solve() 메소드를 각각 실행시키도록 만들어 주었다.

다다음 생각

여기서부터가 문제였던것 같다. 1번부터 차례대로 나간다면 생각하기 쉽겠지만 회전 톱니바퀴번호가 무작위로 주어진다. 처음에는 반복문을 통해 회전하라 주어진 번호의 양옆을 확인하고 또 반복문을 돌면서 확인하게 구현하려 하였지만 쉽지 않았다.

다다다음 생각

앞선 방법이 쉽지 않아 생각을 하다 한 톱니바퀴를 기준으로 연쇄적으로 양옆으로 1칸씩 뻗어나가는 모습이 BFS로 구현할 수 있겠다란 생각이 들었고 BFS로 구현을 하였다.

다다다다음 생각

돌기위해 생각해야 하는 것들을 적어보면

1) 톱니바퀴의 번호

2) 해당 톱니바퀴의 왼쪽 - 왼쪽 톱니바퀴의 오른쪽

3) 해당 톱니바퀴의 오른쪽 - 오른쪽 톱니바퀴의 왼쪽

4) 시계 방향인가 반 시계 방향인가

로 정리 할 수 있을 것이다.

다다다다다음 생각

BFS를 통해 해당 톱니바퀴의 번호에 +1할 경우와 -1할 경우 범위를 따져주고, 가능하다면 위의 2), 3) 번에 해당하는 체크 작업을 하여 만족을 한다면 다음 톱니바퀴가 회전해도 된다는 것이므로 queue에 넣어주었다.

다다다다다다음 생각

회전 방향은 해당 톱니바퀴를 기준으로 다음 톱니바퀴는 무조건 반대 방향이므로 -1을 곱해주었다. 그리고 queue에 들어간 톱니바퀴는 모두 끝에 해당 방향을 가지고 돌려주었다. 미리 돌리지 않은 이유는 바로 위의 생각(같은 톱니인지 아닌지)를 따져야 하기 때문에 모두 따진 후 회전을 시켜주었다.

방안

1) 탐색을 할 때 방문 표시를 안해주었더니 +1 -1 하는 과정에서 자신으로 돌아올 수 있기 때문에 방문 배열로 방문 체크를 추가하였다.

2) 마지막에 각 바퀴 순으로 1,2,4,8을 곱한 결과를 더해야 하므로 배열로 미리 선언해 주었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static int[][] arr = new int[4][8];
    static int k;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 톱니 입력 받기
        for(int i=0;i<4;i++) {
            String t = br.readLine();
            for(int j=0;j<8;j++)
                arr[i][j] = t.charAt(j)-'0';
        }
        // 회전 수
        k = Integer.parseInt(br.readLine());
        // 복합 적으로 도는것이 아니라 한 회전씩 도는 것이므로
        // 한 케이스씩 처리하였다.
        for(int i=0;i<k;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            solve(Integer.parseInt(st.nextToken())-1,Integer.parseInt(st.nextToken()));
        }
        int result = 0;
        int[] mul = {1,2,4,8};
        for(int i=0;i<4;i++) 
            result += arr[i][0]*mul[i];
        
        System.out.println(result);
    }
    
    // 톱니의 왼쪽은        6 번 인덱스
    // 톱니의 오른쪽은    2 번 인덱스
    // 12시 방향은 0 번 인덱스
    // r = 1 시계 , -1 반시계
    private static void solve(int n,int r) {
        boolean[] visited = new boolean[4];
        // BFS가 한 칸씩 전진하므로 BFS로 옆 톱니들을 보자
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(n, r));
        visited[n] = true;
        while(!queue.isEmpty()) {
            Pair t = queue.poll();
            int tt = t.n;
            // 현 기준에서 오른쪽 값 value로
            if(tt+1<4 && !visited[tt+1]) {
                // 다음 꺼랑 톱니가 같지 않다면 돌려야하니 넣어준다.
                if(arr[tt][2]!=arr[tt+1][6])
                    queue.add(new Pair(tt+1,-t.r));
                visited[tt+1] = true;
            }
            // 현 기준에서 왼쪽 값을 value로
            if(tt-1>=0 && !visited[tt-1]) {
                if(arr[tt][6]!=arr[tt-1][2])
                    queue.add(new Pair(tt-1,-t.r));
                visited[tt-1] = true;
            }
            swap(tt,t.r);
        }
    }
    
    private static void swap(int n,int r) {
        if(r==1) {
            // 시계 방향이니 맨 뒤에껄 저장하고
            int t = arr[n][7];
            for(int i=6;i>=0;i--)
                arr[n][i+1] = arr[n][i];
            arr[n][0] = t;
        }else {
            // 반 시계 방향이니 맨 앞에껄 저장하고
            int t = arr[n][0];
            for(int i=1;i<=7;i++)
                arr[n][i-1] = arr[n][i];
            arr[n][7] = t;
        }
    }
    
    static class Pair{
        private int n,r;    
        public Pair(int n,int r) {
            this.n = n;
            this.r = r;
        }
    }
}