1. 문제에 대하여 📦

문제 링크: https://www.acmicpc.net/problem/14891

(1) 조건 분석 📊

날이 8개인 톱니바퀴가 4개 존재하고, 날마다 N극, S극이 있다.
해당 톱니바퀴들은 횡으로 나열되어 있고, 서로의 3시와 9시 날의 극이 서로에게 영향을 준다.
- 현재 내가 조회 중인 톱날의 3시와 그것의 오른쪽 톱날의 9시가 서로 전자극 영향을 받는다.
- 현재 내가 조회 중인 톱날의 9시와 그것의 왼쪽 톱날의 3시가 서로 전자극 영향을 받는다.
특정 톱니바퀴는 시계방향, 반시계방향으로 회전할 수 있다. 한 번의 회전당 날이 한 번 위치를 바꾼다.
톱니바퀴가 회전하면, 그것과 영향을 받는 이웃 톱니바퀴가 서로 3시, 9시 방향에서 전자극이 다르면, 이웃 받는 톱니바퀴는 반대로 돌아간다.
(문제 그림 확인 바람)

2. 코드가 나오기까지 🛠️

KEY WORD: 시뮬레이션, 재귀

현재 돌려야할 톱니바퀴의 이웃 바퀴들이 전자극을 받아 반대방향으로 돌아가는지 체크한다.
1. 이때 기계적으로 이웃만 체크하면 안된다. 이웃 톱니바퀴가 돈다면, 그것의 이웃들 또한 그 영향을 받아 돌아갈 수 있기 떄문이다. 따라서 재귀 로 첫 조회 톱니바퀴 부터 그것의 이웃 톱니바퀴들을 이웃이 더 이상 안 돌아갈 때까지 확인한다.
1번을 하며, 각 톱니바퀴가 돌아갈 방향을 기록해둔다. 이후 해당 방향에 맞게 각각 돌린다ㅏ.
이것을 R번 반복하고 점수 계산

(1) 시간복잡도 분석 ⏳

톱니바퀴가 4개로 고정, 회전도 최대 100번 이므로, 재귀를 써도 문제 없을 듯 하다.

3. 코드 🌐

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

public class Main {
    static int [][] wheels = new int [4][8];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for(int i = 0; i < 4; i++){
            String row = br.readLine();
            for(int j = 0; j < 8; j++) {
                wheels[i][j] = row.charAt(j) - 48;
            }
        }
        int R = Integer.parseInt(br.readLine());
        for(int i = 0; i < R; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken()) - 1;
            int dir = Integer.parseInt(st.nextToken());
            calculate(num, dir);
        }

        int sum = 0;
        if(wheels[0][0] == 1) sum += 1;
        if(wheels[1][0] == 1) sum += 2;
        if(wheels[2][0] == 1) sum += 4;
        if(wheels[3][0] == 1) sum += 8;

        System.out.println(sum);
    }

    public static void calculate(int num, int dir) {
        int [] rotateDir = new int [4];
        checkNS(rotateDir, num, dir); // 극이 다른지 확인

        for(int i = 0; i < 4; i++){
            if(rotateDir[i] != 0) rotate(i, rotateDir[i]);
        }
    }

    public static void checkNS(int [] rotateDir, int num, int dir) {

        if(num < 0 || num >= 4) return;
        rotateDir[num] = dir;
        if(num - 1 >= 0 && wheels[num-1][2] != wheels[num][6] && rotateDir[num - 1] == 0) {
            checkNS(rotateDir, num - 1, dir == 1 ? -1 : 1);
        }
        if(num + 1 < 4 && wheels[num][2] != wheels[num+1][6] && rotateDir[num+1] == 0) {
            checkNS(rotateDir, num + 1, dir == 1? -1 : 1);
        }

    }

    public static void rotate(int num, int dir){
        if(dir == 1) {
            int temp = wheels[num][7];
            int iter = 6;
            while(iter >= 0){
                wheels[num][iter+1] = wheels[num][iter];
                iter--;
            }
            wheels[num][0] = temp;
        }

        if(dir == -1) {
            int temp = wheels[num][0];
            int iter = 1;
            while (iter < 8) {
                wheels[num][iter-1] = wheels[num][iter];
                iter++;
            }
            wheels[num][7] = temp;
        }
    }
}