2 분 소요

문제

문제 바로가기

입력

첫째 줄에 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점

접근방법

  • circle 배열에 각각의 톱니바퀴의 상태를 저장하고, target 배열에 각 톱니바퀴의 3시와 9시방향에 위치한 circle 배열의 인덱스 번호를 저장했다.

  • dfs 함수는 회전시킨 톱니바퀴에 인접한 왼쪽 바퀴부터 검사하고 그 다음 오른쪽 바퀴를 검사하는 방식으로 깊이우선탐색을 통해 재귀 호출을 하는 구조로 만들었다.

  • 서로 맞닿아있는 부분이 다르면 target 배열의 값을 반시계 방향으로 한 칸 조정하고, visited 배열에 검사한 톱니바퀴를 true로 구분해주었다.

  • 위와 동일한 방법으로 K번 반복해서 최종적으로 target 배열에 저장된 인덱스 번호를 이용해 12시 방향의 인덱스 번호를 구했다.

풀이

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

public class Main {
    static int[][] circle;
    static int[][] target;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        circle = new int[4][8];
        target = new int[4][2];
        visited = new boolean[4];

        for(int i = 0; i < 4; i++) {
            String input = br.readLine();
            for(int j = 0; j < 8; j++) {
                circle[i][j] = input.charAt(j) - '0';
            }
            target[i][0] = 6;
            target[i][1] = 2;
        }

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

        for(int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken()) - 1;
            int dict = Integer.parseInt(st.nextToken());

            dfs(num, dict);

            for(int j = 0; j < 4; j++) {
                visited[j] = false;
            }
        }

        int sum = 0;
        int score = 1;
        for(int i = 0; i < 4; i++) {
            int a = (target[i][0] + 2) % 8;
            if(circle[i][a] == 1) {
                sum += score;
            }
            score *= 2;
        }

        System.out.println(sum);
    }

    public static void dfs(int num, int dict) {
        visited[num] = true;
        if(num-1 >= 0 && !visited[num-1]) {
            int a = target[num][0];
            int b = target[num-1][1];
            if(circle[num][a] != circle[num-1][b]) {
                dfs(num-1, -dict);
            }
        }
        if(num+1 < 4 && !visited[num+1]) {
            int a = target[num][1];
            int b = target[num+1][0];
            if(circle[num][a] != circle[num+1][b]) {
                dfs(num+1, -dict);
            }
        }
        int a = target[num][0] - dict;
        int b = target[num][1] - dict;
        a = a < 0 ? 7 : a;
        b = b < 0 ? 7 : b;
        target[num][0] = a % 8;
        target[num][1] = b % 8;
    }
}

댓글남기기

참고