[백준] 톱니바퀴 - Java

문제 링크

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

문제

문제 링크 참조

입력

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.

다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

출력

총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.

• 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
• 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
• 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
• 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

알고리즘: 구현, 시뮬레이션, 재귀

풀이

이 문제를 풀기 위해서 핵심 기능 2가지가 필요하다.

1. 톱니바퀴를 회전시킬 때 같이 회전시켜야 하는 톱니바퀴와 방향을 구하는 메소드

2. 톱니바퀴를 회전했을 때 상태를 업데이트하는 메소드

1번은 재귀를 이용해서 구해준다.
현재 톱니바퀴에서 인접한 톱니바퀴를 체크하는데 회전시켜야 하는 조건이라면 해당 톱니바퀴와 방향을 매개변수로 해서 재귀 호출해준다.
(여기서 주의할 점은 톱니바퀴를 방문 처리 함으로써 무한 호출을 막아줘야 한다.)

2번은 간단하므로 코드 참조

위 메소드를 이용해서 최종 톱니바퀴 상태를 출력하면 된다.

소스 코드

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

class Gear {
    int[] state;
    Gear() {
        this.state = new int[8]; //0 -> 12시, 1 -> 1 30, 2 -> 3
    }
    Gear(int[] state) {
        this.state = state;
    }
}
public class Main {
    static int N;
    static Gear[] gear = new Gear[4];
    static boolean[] visited;
    static int answer = 0;
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        for(int i=0; i<4; i++) {
            gear[i] = new Gear();
            String str_input = sc.nextLine();
            for(int j=0; j<str_input.length(); j++) {
                gear[i].state[j] = str_input.charAt(j) - '0';
            }
        }
        N = sc.nextInt();
        for(int i=0; i<N; i++) {
            visited = new boolean[4];
            rotation_gear(sc.nextInt() - 1, sc.nextInt());
        }
        for(int i=0; i<4; i++) {
            if(gear[i].state[0] == 1) answer += Math.pow(2, i);
        }
        System.out.println(answer);
    }
    
    static void rotation_gear(int gn, int dir) {
        visited[gn] = true;
        int next_dir = dir == 1 ? -1 : 1;
        if(gn == 0) {
            if(!visited[gn + 1] && gear[gn].state[2] != gear[gn + 1].state[6]) {
                rotation_gear(gn + 1, next_dir);
            }
        } else if(gn == 1 || gn == 2) {
            if(!visited[gn - 1] && gear[gn].state[6] != gear[gn - 1].state[2]) {
                rotation_gear(gn - 1, next_dir);
            }
            if(!visited[gn + 1] && gear[gn].state[2] != gear[gn + 1].state[6]) {
                rotation_gear(gn + 1, next_dir);
            }
        } else if(gn == 3) {
            if(!visited[gn - 1] && gear[gn].state[6] != gear[gn - 1].state[2]) {
                rotation_gear(gn - 1, next_dir);
            }
        }
        update_gear(gn, dir);
    }
    
    static void update_gear(int gn, int dir) {
        int[] new_state = new int[8];
        if(dir == 1) {
            //시계
            for(int i=0; i<8; i++) {
                if(i == 0) new_state[i] = gear[gn].state[7];
                else new_state[i] = gear[gn].state[i-1];
            }
        } else {
            //반시계
            for(int i=0; i<8; i++) new_state[i] = gear[gn].state[(i + 1)%8];
        }
        gear[gn] = new Gear(new_state);
    }
}