백준 14891 톱니바퀴

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

public class Gear {
    static int[][] gear;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        gear = new int[4][8];

        for(int i = 0; i<4; i++){
             String input = br.readLine();
            for (int j =0; j<8; j++){
                gear[i][j] = Integer.parseInt(String.valueOf(input.charAt(j)));
            }
        }

        st = new StringTokenizer(br.readLine());
        int num = Integer.parseInt(st.nextToken());
        int [] gearnum = new int[num];
        int [] dir = new int[num];
        for(int i = 0; i<num; i++){
            st = new StringTokenizer(br.readLine());
            gearnum[i] = Integer.parseInt(st.nextToken());
            dir[i] = Integer.parseInt(st.nextToken());
            boolean[] visited = new boolean[4];
            dfs(gearnum[i],dir[i],visited);
        }
        int sum = 0;
        for(int i = 0; i<4; i++){
            if(i==0){
                sum += gear[i][0];
            }
            else if(i==1){
                sum += (2*gear[i][0]);
            }
            else if(i==2){
                sum += (4*gear[i][0]);
            }
            else if(i==3){
                sum += (8*gear[i][0]);
            }
        }
        System.out.println(sum);
    }
    public static void dfs(int gearnum, int dir, boolean[] visited){

        int ngearnum;
        visited[gearnum-1] = true;
        for(int i = 0; i<2; i++){
            if(i==0){
                ngearnum = gearnum+1;
            }
            else {
                ngearnum = gearnum-1;
            }
            if(ngearnum==0||ngearnum==5)
                continue;
            if(visited[ngearnum-1])
                continue;
            if(i==0 && gear[gearnum-1][2]!=gear[ngearnum-1][6]){
                if(dir == -1){
                    dfs(ngearnum,1,visited);
                }
                else if(dir == 1){
                    dfs(ngearnum,-1,visited);
                }
            }
            if(i==1 && gear[gearnum-1][6] != gear[ngearnum-1][2]){
                if(dir == -1){
                    dfs(ngearnum,1,visited);
                }
                else if(dir == 1){
                    dfs(ngearnum,-1,visited);
                }
            }
        }
        int pre = gear[gearnum-1][7];
        int pre2 = gear[gearnum-1][0];
        for(int i = 0; i<8; i++){
            if(dir == -1){
                int next = gear[gearnum-1][7-i];
                gear[gearnum-1][7-i] = pre2;
                pre2 = next;
            }
            else if(dir == 1){
                int next = gear[gearnum-1][i];
                gear[gearnum-1][i] = pre;
                pre = next;
            }
        }

    }

}

풀이방법

1. 일단 톱니바퀴의 정보를 2차원 배열에 넣는다
2. 회전할 톱니바퀴와 회전방향을 dfs에 전달 (이때 전달할때마다 visited변수를 새로 생성해서 전달한다. 이전 방문이 영향을 끼치지 않도록)
3. 현재 톱니바퀴 오른쪽 확인해서 첫방문이고 1~4번째 안에 있고, 극성이 반대면 dfs로 전달, 이때 방향 dir은 반대값으로 전달한다.
4. 현재 톱니바퀴 왼쪽도 똑같이 수행
5. dfs함수 끝에 시계,반시계방향으로 회전하는하는 로직 구현, dfs함수 끝에 구현해서 재귀호출시 바뀐 톱니바퀴 값이 영향가지 않도록(문제가 그렇게 설정되어있음)
6. 마지막에 톱니바퀴 4개 돌면서 문제 조건따라 sum계산