Java 14891 톱니바퀴

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

14891번: 톱니바퀴

 

문제에 대한 설명이 길기에 링크를 걸어두겠습니다.

 

풀이 :

로직은 다음과 같다.

 

1. 회전할 톱니바퀴와 인접한 톱니바퀴의 값을 dfs를 통하여 회전이 필요한 경우 check 배열에 bool값을 업데이트 해준다.

2. 회전이 일어나는 톱니바퀴가 기준이 되는 톱니바퀴와의 인덱스의 차이를 구해 처음 주어진 방향과 똑같이 회전하는지 반대 방향으로 회전하는지를 구하고 회전을 시켜준다.

3. 모든 반복문이 끝났다면 switch 문을 통해 각각의 톱니바퀴의 12시 방향의 원소를 기준으로 score 값을 갱신해준다.

 

dfs를 떠올린 순간부턴 쉽게 풀 수 있었던 거 같습니다.

 

 

 

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

public class Main {
    static boolean[] check;
    static int[] dir = {-1, 1};
    static ArrayList<LinkedList<Integer>> list;
    static void dfs(int index){
        int n = index;

        for(int i = 0; i < 2; i++){
            int cn = n + dir[i];

            if(cn >= 0 && cn < 4 && !check[cn]){
                if(n > cn){
                    if(list.get(n).get(6) != list.get(cn).get(2)){
                        check[cn] = true;
                        dfs(cn);
                    }
                }else {
                    if(list.get(n).get(2) != list.get(cn).get(6)){
                        check[cn] = true;
                        dfs(cn);
                    }
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        list = new ArrayList<>();

        for(int i = 0; i < 4; i++){
            String str = br.readLine();
            list.add(new LinkedList<>());
            for(int j = 0; j < 8; j++){
                list.get(i).addLast(str.charAt(j) - '0');
            }
        }

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

        while(T --> 0){
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken()) - 1 ;
            int direction = Integer.parseInt(st.nextToken());
            boolean flag = false;

            if(direction > 0){
                flag = true;
            }

            check = new boolean[4];
            check[n] = true;
            dfs(n);

            for(int i = 0; i < 4; i++){
                if(check[i]){
                    if((Math.abs(n-i)) % 2 == 0){
                        if(flag){
                            right(i);
                        }else {
                            left(i);
                        }
                    }else {
                        if(flag){
                            left(i);
                        }else {
                            right(i);
                        }
                    }
                }
            }
        }

        int score = 0;
        for(int i = 0; i < 4; i++){
            switch (i){
                case 0 :
                    if(list.get(i).get(0) == 1){
                        score += 1;
                    }
                    break;
                case 1 :
                    if(list.get(i).get(0) == 1){
                        score += 2;
                    }
                    break;
                case 2 :
                    if(list.get(i).get(0) == 1){
                        score += 4;
                    }
                    break;
                case 3 :
                    if(list.get(i).get(0) == 1){
                        score += 8;
                    }
                    break;
            }
        }

        System.out.println(score);
    }


    static void right(int index){
        list.get(index).offerFirst(list.get(index).pollLast());
    }
    static void left(int index){
        list.get(index).offerLast(list.get(index).pollFirst());
    }
}