14891 : 톱니바퀴 python

톱니바퀴를 회전시킬 때는 방향과 회전시킬 톱니바퀴를 선택한다.

톱니바퀴와 맞닿은 다른 톱니바퀴의 극이 서로 다르다면 → 맞닿은 톱니바퀴는 해당 톱니바퀴의 반대방향으로 회전

모든 회전이 끝나면 12시방향이 S극이면 + 2^(N - 1) 점

3번 톱니바퀴는 맞닿아있는 4번 톱니바퀴와 극이 다르다.

1회전 시 3번 톱니바퀴는 반시계, 4번 톱니바퀴가 시계방향으로 움직인다.

이제 1번 바퀴를 시계 방향으로 움직인다. 2번 바퀴와 극이 다르므로 2번은 반시계방향으로 움직인다.

1,2,3번 바퀴가 12시방향에 S극이다. 따라서, 1 + 2 + 4 = 7점

K가 100으로 매우 작음

오른쪽 바퀴 회전 여부 → 현재 바퀴[2]와 다음 바퀴[6]이 서로 다른지 확인

왼쪽 바퀴 회전 여부 → 현재 바퀴[6]과 다음 바퀴[2]가 서로 다른지 확인

 

회전 자체는 재귀 DFS를 통해 구현했는데 처음 선택한 바퀴 양 옆 바퀴들을 확인하면서 가장 마지막으로 영향받는 바퀴를 먼저 회전 시키고 돌아와서 선택한 바퀴를 회전시키도록 했다.

import sys

# print = sys.stdout.write
input = sys.stdin.readline
# f = open("input.txt", "rt")
# input = f.readline

LEFT, RIGHT = 0, 1
ADJ_LEFT, ADJ_RIGHT = 6, 2

cogwheels = (
    [list("00000000")] + [list(input().rstrip()) for _ in range(4)] + [list("00000000")]
)
K = int(input().rstrip())

def main():
    for _ in range(K):
        target, dir = map(int, input().split())
        if dir == 1:  # 시계
            move(target, RIGHT, set())
        else:
            move(target, LEFT, set())

    ans = 0
    for i in range(1, 5):
        if cogwheels[i][0] == "1":
            ans += 2 ** (i - 1)

    print(int(ans))

def move(target, dir, v=set()):
    # 기저 탈출 조건
    if target > 4 or target < 1 or target in v:
        return
    v.add(target)
    if check(target, target + 1, RIGHT):
        move(target + 1, (dir + 1) % 2, v)
    if check(target, target - 1, LEFT):
        move(target - 1, (dir + 1) % 2, v)

    cur = cogwheels[target]
    if dir == RIGHT:  # 시계방향
        spin = cur.pop()
        cur.insert(0, spin)
        return

    spin = cur.pop(0)
    cur.append(spin)

def check(cur, target, dir):
    if dir == RIGHT:  # 오른쪽 바퀴와 비교할 거면
        return cogwheels[cur][ADJ_RIGHT] != cogwheels[target][ADJ_LEFT]

    return cogwheels[cur][ADJ_LEFT] != cogwheels[target][ADJ_RIGHT]

if __name__ == "__main__":
    main()

비트마스킹 풀이

비트마스킹 체크 메서드

ADJ_LEFT, ADJ_RIGHT = 1, 5
def check(cur, target, dir):
    if dir == RIGHT:  # 오른쪽 바퀴와 비교할 거면
        cur = cogwheels[cur] & (1 << ADJ_RIGHT) > 0
        target = cogwheels[target] & (1 << ADJ_LEFT) > 0
        return cur ^ target

    cur = cogwheels[cur] & (1 << ADJ_LEFT) > 0
    target = cogwheels[target] & (1 << ADJ_RIGHT) > 0
    return cur ^ target

비트마스킹에서 체크 메서드는 위와 같다. 위 코드는 선택된 바퀴의 회전 방향에 따라 두 바퀴들을 검사한다.

^ XOR연산은 두 비트를 비교해 두 비트가 서로 다를 경우에만 해당 자리에 1을 반환한다. 따라서, 위와 같이 특정 자리 수를 비교할 때, 두 비트가 서로 다르다면 1 이상의 값을 반환한다. 이렇게 검사한 두 결과를 다시 XOR 연산하면 두 선택한 바퀴와 맞닿은 바퀴가 서로 반대극인지 확인할 수 있다.

 

 

시계방향 회전 알고리즘

3번 톱니바퀴(11001110)에 대해서 반시계방향으로 회전한다면, 가장 큰 자리수인 7번째 자리수를 제외한 모든 자리수가 한 칸씩 앞으로 증가하고 7번째 자리수가 1번째로 이동해야 한다.

print(f"cur = {bin(cur)}") # cur = 0b11001110
    # 가장 큰 자리수 뽑기
    spin = 1 if cur & (1 << 7) > 0 else 0
    # 가장 큰 비트 끄기 (01111111)
    cur = cur & ((1 << 7) - 1)
    print(f"cur = {bin(cur)}") # cur = 0b1001110
    # 한 칸씩 앞으로 증가
    cur = cur << 1
    print(f"cur = {bin(cur)}") # cur = 0b10011100
    # 가장 큰 자리 수 뽑아서 첫 자리수로 이동
    cur |= spin
    print(f"cur = {bin(cur)}") # cur = 0b10011101

반시계방향 회전 알고리즘

3번과 맞물린 4번 톱니바퀴(00000010)는 3번이 시계방향으로 회전함에 따라 반대방향인 반시계 방향으로 회전해야 한다. 이 경우 가장 작은 자리수인 1을 저장한 뒤, 첫 번째 자리 수를 제외한 모든 자리수가 한칸씩 뒤로 이동해야 한다.

if dir == RIGHT:  # 시계방향
    print(f"cur = {bin(cur)}") # cur = 0b10
    # 가장 마지막 수 뽑기
    spin = 1 if cur & 1 > 0 else 0
    # 한칸씩 뒤로 이동
    cur = cur >> 1
    print(f"cur = {bin(cur)}") # cur = 0b1
    # 가장 큰 자리수에 spin 추가
    cur = cur | (spin << 7)
    print(f"cur = {bin(cur)}") # cur = 0b1
    return

시계 방향에서와 다르게 비트를 끄는 코드가 없는데 이는 비트를 오른쪽으로 쉬프트하게 되면 가장 작은 비트는 절삭되기 때문이다. 따라서, 비트를 끌 필요가 없다.

import sys

# print = sys.stdout.write
input = sys.stdin.readline
# f = open("input.txt", "rt")
# input = f.readline

LEFT, RIGHT = 0, 1
# 11001110 배열 기준 6번과 2번
# 2진수 기준 오른쪽으로 1번과 5번
ADJ_LEFT, ADJ_RIGHT = 1, 5

cogwheels = [int(input().rstrip(), 2) for _ in range(4)]
K = int(input().rstrip())

def main():
    for _ in range(K):
        target, dir = map(int, input().split())
        v = 0
        if dir == 1:  # 시계
            move(target - 1, RIGHT, v)
        else:
            move(target - 1, LEFT, v)

    ans = 0
    for i in range(4):
        if cogwheels[i] & (1 << 7):
            ans |= 1 << i

    print(ans)

def move(target, dir, v):
    # 기저 탈출 조건
    if (v & (1 << target)) > 0:
        return
    v |= 1 << target

    if target + 1 <= 3 and check(target, target + 1, RIGHT):
        move(target + 1, (dir + 1) % 2, v)
    if target - 1 >= 0 and check(target, target - 1, LEFT):
        move(target - 1, (dir + 1) % 2, v)

    if dir == RIGHT:  # 시계방향
        spin = 1 if cogwheels[target] & 1 > 0 else 0
        cogwheels[target] = (cogwheels[target] >> 1) | (spin << 7)
        return

    spin = 1 if cogwheels[target] & (1 << 7) > 0 else 0
    cogwheels[target] = ((cogwheels[target] & ((1 << 7) - 1)) << 1) | spin

def check(cur, target, dir):
    if dir == RIGHT:  # 오른쪽 바퀴와 비교할 거면
        cur = cogwheels[cur] & (1 << ADJ_RIGHT) > 0
        target = cogwheels[target] & (1 << ADJ_LEFT) > 0
        return cur ^ target

    cur = cogwheels[cur] & (1 << ADJ_LEFT) > 0
    target = cogwheels[target] & (1 << ADJ_RIGHT) > 0
    return cur ^ target

if __name__ == "__main__":
    main()