[백준 14891] 톱니바퀴

문제 보기

이 문제는 시뮬레이션 문제이다.

톱니바퀴의 초기상태와 회전 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구해야한다.

나는 이 문제를 보자마자 나는 비트마스크를 써야겠다고 생각했다.

톱니의 상태를 2진수로 만들고, 이를 시계방향, 반시계방향으로 회전시키는 함수를 만들었다. (10~25번째 줄)

12시 방향의 비트를 MSB로 두었고, MSB 바로 왼쪽의 비트를 LSB로 두었다.

10101111 -> 01011111

각 명령마다 톱니바퀴를 선택하고 돌릴 때, solution 함수를 통해 톱니바퀴를 양쪽으로 탐색한다.

비트마스크를 사용해서 문제를 풀 때, 여기서 주의해야할 점이 있다.

1. 오른쪽으로 탐색할 때

오른쪽 톱니바퀴를 회전시킬지 결정할 때, 오른쪽 톱니바퀴의 2번째 비트와, 왼쪽 톱니바퀴의 6번째 비트를 비교한다. 만약 비트가 다르다면 왼쪽 톱니바퀴의 반대방향으로 회전시킨다.

2. 왼쪽으로 탐색할 때

왼쪽 톱니바퀴를 회전시킬지 결정할 때, 왼쪽 톱니바퀴의 6번째 비트와, 오른쪽 톱니바퀴의 2번째 비트를 비교한다. 만약 비트가 다르다면 오른쪽 톱니바퀴의 반대반향으로 회전시킨다.

32~40번째 줄을 보면, 톱니바퀴의 탐색 방향과 비트 일치유무에 따라 flag를 지정하고, 이를 재귀적으로 처리한다.

import sys
 
gear = list()
for i in range(4):
    gear.append(int('0b' + sys.stdin.readline(), 2))
k = int(sys.stdin.readline())
command = [list(map(int, sys.stdin.readline().split())) for i in range(k)]
 
 
def turn_counter_clockwise(num):
    a = num
    temp = (a >> 7) & 1
    a <<= 1
    a |= temp
    a &= (1 << 8) - 1
    return a
 
 
def turn_clockwise(num):
    a = num
    temp = a & 1
    a >>= 1
    a |= (temp << 7)
    a &= (1 << 8) - 1
    return a
 
 
def solution(idx, _clockwise, direction):
    if idx < 0 or idx > 3:
        return
    
    # right traverse
    if direction == 1:
        a = (gear[idx] & (1 << 1)) >> 1
        b = (gear[idx - direction] & (1 << 5)) >> 5
    # left traverse
    elif direction == -1:
        a = (gear[idx] & (1 << 5)) >> 5
        b = (gear[idx - direction] & (1 << 1)) >> 1
    flag = True if a != b else False
    
    if flag:
        solution(idx + direction, not _clockwise, direction)
        
        if _clockwise:
            gear[idx] = turn_clockwise(gear[idx])
        else:
            gear[idx] = turn_counter_clockwise(gear[idx])
 
 
for i in range(k):
    start = command[i][0] - 1
    clockwise = True if command[i][1] == 1 else False
    
    # left traverse
    solution(start - 1, not clockwise, -1)
    # right traverse
    solution(start + 1, not clockwise, 1)
    
    if clockwise:
        gear[start] = turn_clockwise(gear[start])
    else:
        gear[start] = turn_counter_clockwise(gear[start])
 
answer = 0
for i in range(4):
    answer += (gear[i] & (1 << 7)) >> (7 - i)
print(answer)