톱니바퀴

In [1]:

import sys, random
sys.path.append("/home/swyoo/algorithm/")
from utils.verbose import logging_time
from utils.generator import random2D
from sys import stdin
from copy import deepcopy
import numpy as np

14891. 톱니바퀴

Beakjoon의 문제.
톱니바퀴를 돌리는 문제, 톱니 바퀴는 4개이며 각 바퀴의 톱니는 8개씩 있다.

saws의 각 톱니바퀴는 시계방향(clock-wise)와 반시계방향(counter-clock-wise)로 돌릴 수 있으며
moves 로 돌릴 톱니바퀴의 index와 방향(direction) 이 주어진다.

주의사항은 문제에서 주어진 톱니바퀴의 index는 번째 수 이므로 -1을 하여 전처리한다.
돌리는 방향은 1은 시계방향(clock-wise), -1은 반시계방향(counter-clock-wise)이다.

In [2]:

plot = lambda a: print(np.array(a))
stdin = open('data/saws.txt')
input = stdin.readline
saws = [list(map(int, input().strip())) for _ in range(4)]
k = int(input())
moves = [list(map(int, input().split())) for _ in range(k)]
moves = list(map(lambda x: (x[0] - 1, x[1]), moves))
direct = [(7, 0, 1, 2, 3, 4, 5, 6),  # clock-wise (->)
          (1, 2, 3, 4, 5, 6, 7, 0)]  # counter-clock-wise (<-)
left, right, up = 6, 2, 0

plot(saws)
print(moves)

[[1 0 1 0 1 1 1 1]
 [0 1 1 1 1 1 0 1]
 [1 1 0 0 1 1 1 0]
 [0 0 0 0 0 0 1 0]]
[(2, -1), (0, 1)]

Idea

각 톱니바퀴를 주어진 명령에 따라 회전시킬 수 있도록 한다.

톱니바퀴의 adjacent list를 Hard Coding하고, dfs를 통해 연속적으로 움직이도록 한다.
이때 주의해야할 점은 톱니바퀴의 왼쪽(index=6)과 오른쪽(right, index=2)의 극성 S극(1) N극(0)을 보고
회전 방향이 결정된다.

Step1. Rotate a Saw

0번째 톱니 saws[0]을 회전시켜 보았다.

• kind = 1: clock-wise
• kind = -1: counter-clock-wise

In [3]:

def rotate(a, kind):
    idx = 0 if kind == 1 else 1
    return [a[direct[idx][x]] for x in range(8)]

def saw2plot(saw):
    a = [[-1] * 3 for _ in range(3)]
    a[0][1], a[0][2], a[1][2], a[2][2], a[2][1], a[2][0], a[1][0], a[0][0] = saw
    plot(a)

print(saws[0], 'is as follows. ')
saw2plot(saws[0])
print("rotate according to clock-wise as follows.")
saw2plot(rotate(saws[0], 1))  # -> 방향 회전
print("rotate according to counter-clock-wise as follows.")
saw2plot(rotate(saws[0], -1))  # <- 방향 회전

[1, 0, 1, 0, 1, 1, 1, 1] is as follows. 
[[ 1  1  0]
 [ 1 -1  1]
 [ 1  1  0]]
rotate according to clock-wise as follows.
[[ 1  1  1]
 [ 1 -1  0]
 [ 1  0  1]]
rotate according to counter-clock-wise as follows.
[[ 1  0  1]
 [ 1 -1  0]
 [ 1  1  1]]

Step2. DFS

DFS를 통해 연속된 회전 구현.

주의사항

1. adjacent list구현시, 톱니의 idex이외에도 오른쪽에서 온건지 왼쪽에서 온건지 notification필요.
2. 돌리기 전에 L, R의 상태를 저장해 놓아야 한다. 이유는 다음과 같다.
2 - 1. adjacent한 톱니 saws[j]를 돌릴지 말지의 여부
2 - 2. L != saws[j][right] 또는 R != saws[j][left] 이면 saws[i]의 회전방향 kind와 반대로 돌린다.

In [4]:

@logging_time
def solution(saws, moves, show=False):
    adj = {0: [(1, right)],
           1: [(0, left), (2, right)],
           2: [(1, left), (3, right)],
           3: [(2, left)]}

    def dfs(i, kind, seen):
        seen.add(i)
        L, R = saws[i][left], saws[i][right]
        saws[i] = rotate(saws[i], kind)
        for j, opp in adj[i]:
            if j not in seen:
                if opp == left and L != saws[j][right]:
                    dfs(j, -kind, seen)
                elif opp == right and R != saws[j][left]:
                    dfs(j, -kind, seen)

    for sidx, kind in moves:
        dfs(sidx, kind, set())
        if show: 
            print("move a saw [{}] according to the direction [{}]".format(sidx, kind))
            for k, saw in enumerate(saws):
                print('saw[{}] is as follows.'.format(k)), saw2plot(saw)

    ans = 0
    for i in range(4):
        if saws[i][up]:
            ans += 2 ** i
    return ans


print("ans:", solution(saws, moves, show=True, verbose=True))

move a saw [2] according to the direction [-1]
saw[0] is as follows.
[[ 1  1  0]
 [ 1 -1  1]
 [ 1  1  0]]
saw[1] is as follows.
[[ 1  0  1]
 [ 0 -1  1]
 [ 1  1  1]]
saw[2] is as follows.
[[ 1  1  0]
 [ 0 -1  0]
 [ 1  1  1]]
saw[3] is as follows.
[[ 1  0  0]
 [ 0 -1  0]
 [ 0  0  0]]
move a saw [0] according to the direction [1]
saw[0] is as follows.
[[ 1  1  1]
 [ 1 -1  0]
 [ 1  0  1]]
saw[1] is as follows.
[[ 0  1  1]
 [ 1 -1  1]
 [ 0  1  1]]
saw[2] is as follows.
[[ 0  1  1]
 [ 1 -1  0]
 [ 1  1  0]]
saw[3] is as follows.
[[ 1  0  0]
 [ 0 -1  0]
 [ 0  0  0]]
WorkingTime[solution]: 1.74212 ms
ans: 7

Time Complexity

moves size를 $n$ 이라 하였을때,

1. Rotate: $O(1)$
2. A dfs(i) call: at most 4 time visit, so $O(1)$

Therefore, $O(n)$

Test Cases

Generate test datasets and get the ans.

In [5]:

size = 1000000
saws = random2D(shape=(4,8), randrange=(0, 1))
moves = [(random.choice(range(4)), random.choice([1, -1])) for _ in range(size)]
plot(saws)
plot(moves)

print("ans:", solution(saws, moves, verbose=True))

[[0 0 1 0 0 1 0 0]
 [1 1 1 0 0 1 0 1]
 [0 0 0 0 1 0 1 1]
 [0 1 0 1 0 0 1 0]]
[[ 1  1]
 [ 2  1]
 [ 2 -1]
 ...
 [ 2  1]
 [ 0  1]
 [ 0  1]]
WorkingTime[solution]: 4199.79739 ms
ans: 2

Submitted Code

In [6]:

from sys import stdin
from copy import deepcopy

stdin = open('data/saws.txt')
input = stdin.readline
saws = [list(map(int, input().strip())) for _ in range(4)]
k = int(input())
moves = [list(map(int, input().split())) for _ in range(k)]
moves = list(map(lambda x: (x[0] - 1, x[1]), moves))
direct = [(7, 0, 1, 2, 3, 4, 5, 6),  # clock-wise
          (1, 2, 3, 4, 5, 6, 7, 0)]  # counter-clock-wise

def rotate(a, kind):
    idx = 0 if kind == 1 else 1
    return [a[direct[idx][x]] for x in range(8)]
left, right, up = 6, 2, 0


def solution(saws, moves):
    adj = {0: [(1, right)],
           1: [(0, left), (2, right)],
           2: [(1, left), (3, right)],
           3: [(2, left)]}

    def dfs(i, kind, seen):
        seen.add(i)
        L, R = saws[i][left], saws[i][right]
        saws[i] = rotate(saws[i], kind)
        for j, opp in adj[i]:
            if j not in seen:
                if opp == left and L != saws[j][right]:
                    dfs(j, -kind, seen)
                elif opp == right and R != saws[j][left]:
                    dfs(j, -kind, seen)

    for sidx, kind in moves:
        dfs(sidx, kind, set())

    ans = 0
    for i in range(4):
        if saws[i][up]:
            ans += 2 ** i
    return ans


print(solution(saws, moves))

7