문제

BOJ 14891, 톱니바퀴

핵심

• 입력의 크기가 $10^2$이라 구현에 초점을 맞춘다.
• 8개의 톱니를 가지고 있는 톱니바퀴 4개가 있고, 각각의 톱니는 N(0) 또는 S(1)극을 향하고 있다. 특정 톱니바퀴를 시계방향이나 반시계 방향으로 회전시켰을 때 양옆에 있는 톱니바퀴와 가리키는 극이 다르다면 같이 회전하는 데 반대 방향으로 회전한다. 그림으로 나타내면 다음과 같다.
  
• 위의 그림에서 세 번째 톱니바퀴를 시계방향으로 회전시킬 때, 네 번째 톱니바퀴와 가리키는 극이 다르다면 네 번째 톱니바퀴는 반시계 방향으로 회전한다.
• 구현 문제답게 조심해야 할 부분이 있다. 3번 톱니바퀴를 회전시키고 나서 양옆에 톱니바퀴와 비교하면 안 된다. 회전시키기 전에 양옆에 톱니바퀴 중 회전이 가능한 부분을 미리 검사해야 한다.
• 크게 구현 사항이 2가지가 있다. 시계방향과 반시계방향 회전, 회전시키기 전에 주변 톱니바퀴의 회전 여부를 검사해야 한다.
• 첫째로 회전을 구현해 보자. 톱니 바퀴는 12시 방향부터 총 8개의 톱니가 0(N), 1(S)로 입력된다. 시계방향 회전은 한 칸씩 오른쪽으로 미는 것이다. 가장 끝 톱니가 처음으로 온다. 반시계 방향 회전은 반대로 왼쪽으로 한 칸씩 미는 것이고, 가장 처음 톱니가 가장 뒤로 간다. 이를 구현하면 다음과 같다.

void rotateClockwise(int num) {
	char last = wheel[num].back();
	wheel[num].pop_back();
	wheel[num].insert(0, 1, last);
}

void rotateCounterClockwise(int num) {
	char first = wheel[num].front();
	wheel[num].erase(0, 1);
	wheel[num].push_back(first);
}

• 둘째로 회전시키기 전에 왼쪽 톱니와 오른쪽 톱니를 비교하여 서로 가리키는 극이 다르다면, 반대 방향으로 회전시키는 것을 기록해야 한다. 이를 위해 rotation 배열을 선언하고, 특정 톱니의 회전 방향을 저장한다. 예를 들어 rotation[4] = -1 는 4번 톱니바퀴가 반시계 방향으로 회전시킨다는 뜻이다. 회전 시키는 기준 톱니를 기준으로 영향을 받는 왼쪽 톱니를 판단하기 위해선 기준 톱니바퀴의 톱니[6]과 왼쪽 톱니바퀴의 톱니[2]를 확인해야 한다. 반대로 영향을 받는 오른쪽 톱니를 판단하기 위해선 기준 톱니바퀴의 톱니[2]와 오른쪽 톱니[6]를 확인해야 한다. 이해가 안 된다면 위에 그림을 참고하자. 코드로 나타내면 아래와 같다.

void checkRotation(int num, int direct) {
	int dir = direct;
	for (int left = num - 1; left >= 1; --left) {
		int cur = left + 1;
		if (wheel[left][2] != wheel[cur][6]) {
			dir *= -1;
			rotation[left] = dir;
		} else
			break; 
	}
	dir = direct;
	for (int right = num + 1; right <= 4; ++right) {
		int cur = right - 1;
		if (wheel[right][6] != wheel[cur][2]) {
			dir *= -1;
			rotation[right] = dir;
		} else
			break; 
	}
}

• 여기에서 착각하기 쉬운 건 영향을 받는 오른쪽 톱니를 계산할 때, dir = direct를 한 번 더 해주어야 한다는 것이다. 그 이유는 영향을 받는 왼쪽 톱니의 개수가 홀수일 때, 기준 톱니의 오른쪽 톱니가 기준톱니와 방향이 똑같을 수 있기 때문이다. 내가 맞왜틀? 했던 부분이다.

개선

• 만약 기준 톱니가 오른쪽으로 회전할 때, 1칸이 아니라 2칸씩 이동한다면? 2칸이 아니라 6칸씩 이동한다면 이를 어떻게 구현해야 할까? 물론 일일이 다 구현할 수도 있겠지만 각 언어에선 rotate 함수를 지원한다. 사용법을 간단한 예시와 함께 알아보자.
• 시계 방향으로 1칸 회전

rotate(wheel[i].begin(), wheel[i].begin() + 1, wheel[i].end());   

Collections.rotate(wheels[i], 1);

• 반시계 방향으로 1칸 회전(C++)

// 8개의 문자 중 7개의 문자를 wheel[i].end()로 보낸다
rotate(wheel[i].begin(), wheel[i].begin() + 7, wheel[i].end());

Collections.rotate(wheels[i], -1);

코드

시간복잡도

• 대략 $O(100 * 4^2)$

C++

#include <iostream>
using namespace std;

string wheel[7];
int rotation[7];
void rotateClockwise(int num) {
	char last = wheel[num].back();
	wheel[num].pop_back();
	wheel[num].insert(0, 1, last);
}

void rotateCounterClockwise(int num) {
	char first = wheel[num].front();
	wheel[num].erase(0, 1);
	wheel[num].push_back(first);
}

void checkRotation(int num, int direct) {
	int dir = direct;
	for (int left = num - 1; left >= 1; --left) {
		int cur = left + 1;
		if (wheel[left][2] != wheel[cur][6]) {
			dir *= -1;
			rotation[left] = dir;
		} else
			break; 
	}
	dir = direct;
	for (int right = num + 1; right <= 4; ++right) {
		int cur = right - 1;
		if (wheel[right][6] != wheel[cur][2]) {
			dir *= -1;
			rotation[right] = dir;
		} else
			break; 
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	for (int i = 1; i <= 4; ++i) cin >> wheel[i];
	int k;
	cin >> k;
	while (k--) {
		int num, dir;
		cin >> num >> dir;
		fill(rotation, rotation + 7, 0);
		rotation[num] = dir;
		checkRotation(num, dir);
		for (int i = 1; i <= 4; ++i) {
			if (rotation[i] == 0) continue;
			if (rotation[i] == 1)
				rotateClockwise(i);			
			else 
				rotateCounterClockwise(i);
		}
	}
	int score = 0;
	for (int i = 1; i <= 4; ++i) {
		if (wheel[i][0] == '1')
			score += (1 << (i - 1));
	}
	cout << score;
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static ArrayList<ArrayList<Integer>> wheel = new ArrayList<>();
    static int[] rotation = new int[7];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 0; i < 4; ++i) {
            ArrayList<Integer> wheelRow = new ArrayList<>();
            String nums = br.readLine();
            for (var c : nums.toCharArray())
                wheelRow.add(c - '0');
            wheel.add(wheelRow);
        }
        int k = Integer.parseInt(br.readLine());
        while (k-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int num = Integer.parseInt(st.nextToken()) - 1;
            int dir = Integer.parseInt(st.nextToken());
            Arrays.fill(rotation, 0);
            rotation[num] = dir;
            checkrotation(num, dir);
            for (int i = 0; i < 4; i++) {
                if (rotation[i] == 0) continue;
                Collections.rotate(wheel.get(i), rotation[i]);
            }
        }
        int score = 0;
        for (int i = 0; i < 4; i++) {
            if (wheel.get(i).get(0) == 1)
                score += 1 << i;
        }
        System.out.println(score);
        br.close();
    }

    static void checkrotation(int num, int direct) {
        int dir = direct;
        for (int left = num - 1; left >= 0; --left) {
            int cur = left + 1;
            if (wheel.get(left).get(2) != wheel.get(cur).get(6)) {
                dir *= -1;
                rotation[left] = dir;
            } else
                break;
        }
        dir = direct;
        for (int right = num + 1; right < 4; ++right) {
            int cur = right - 1;
            if (wheel.get(right).get(6) != wheel.get(cur).get(2)) {
                dir *= -1;
                rotation[right] = dir;
            } else
                break;
        }
    }
}