[backjoon]14891 톱니바퀴 java

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

14891번: 톱니바퀴

DFS를 이용해서 풀이해줘야 하는 문제.

원형이라 생각하여 어떻게 구현해야 하나 막막했지만

마주하는 부분의 값이 같을 때 회전하지 않고, 마주하는 부분이 다를 때 계속 회전하는 부분을 잘 생각해서 풀이하면 된다.

1. 계속해서 파고 들어가는 점에서 깊이 우선 탐색(DFS)해야 한다.

2. 종료 조건은 톱니를 벗어날 때(인덱스가 -1 이하거나 4 이상인 경우)와 마주하는 부분(N-N, S-S)이 같아질 때지만 양방향을 탐색해야 하기 때문에 조건에 해당하는 경우만 탐색하는 방식으로 구현해 줘야 한다.

마주하는 부분에 대한 것도 문제에서 순서를 이미 정해줬기 때문에 12시 방향이 0이고 시계 방향으로 값이 커짐을 확인한다면 2번 6번 인덱스를 확인해주면 되는 것을 알 수 있다. 

3. 또한 그림에서 확인할 수 있듯이 한 회전당 한 번만 움직이기에 움직일 톱니바퀴를 기록해줘서 한 번만 회전시켜 줘야 한다.(boolean[] marked/int[] turnArr)

4. 회전하는 부분은 한 칸씩 왼쪽으로 값을 바꿔주거나 오른쪽으로 값을 이동시키면 된다. (turn())

 

 

//https://www.acmicpc.net/problem/14891
import java.io.*;
import java.util.*;
 
class Main {
    static char[][] wheels;
    static boolean[] marked;
    static int[] turnArr;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        wheels = new char[4][8];
        for (int i = 0; i < 4; i++) {
            String str = br.readLine();
            wheels[i] = str.toCharArray();
        }
 
        st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int row = Integer.parseInt(st.nextToken()) - 1;
            int dir = Integer.parseInt(st.nextToken());
            marked = new boolean[4];
            turnArr = new int[4];
 
            dfs(row, dir);
            wheels = turn();
 
        }
 
        int sum = 0;
        int point = 1;
        for (int i = 0; i < 4; i++) {
            int cur = wheels[i][0];
            if ('1' == cur)
                sum += point;
            point *= 2;
        }
        System.out.println(sum);
    }
 
    public static char[][] turn() {
        char[][] result = new char[4][8];
 
        for (int idx = 0; idx < 4; idx++) {
            if (turnArr[idx] == -1) {//시계 반대 방향
                for (int i = 0; i < 7; i++) {
                    result[idx][i] = wheels[idx][i + 1];
                }
                result[idx][7] = wheels[idx][0];
            } else if (turnArr[idx] == 1) {//시계 방향
                for (int i = 0; i < 7; i++) {
                    result[idx][i + 1] = wheels[idx][i];
                }
                result[idx][0] = wheels[idx][7];
            } else {//변화 없음.
                for (int i = 0; i < 8; i++) {
                    result[idx][i] = wheels[idx][i];
                }
            }
        }
        return result;
    }
 
    public static void dfs(int row, int dir) {
        marked[row] = true;
        turnArr[row] = dir;
        if (row < 3 && !marked[row + 1] && wheels[row][2] != wheels[row + 1][6])
            dfs(row + 1, dir * -1);
        if (row > 0 && !marked[row - 1] && wheels[row - 1][2] != wheels[row][6])
            dfs(row - 1, dir * -1);
    }
}