[python] 14891 - 톱니바퀴

14891번: 톱니바퀴 (acmicpc.net)

14891번: 톱니바퀴

 

문제 접근의 시작은 어떤 구조를 쓸지 파악하는 것이었다.

1. 리스트를 사용해야하는데 회전해야한다? -> deque을 사용!

2. 회전시키는 톱니바퀴를 기준으로 하여 좌우 톱니바퀴들을 돌려주어야한다.

   2-1. 톱니바퀴를 돌릴지 안돌릴지 판단하자.

   2-2. 톱니바퀴를 돌려야 한다면 재귀를 사용하자.

 

 

여기까지가 처음 시작한 접근이었다.

톱니바퀴의 개수는 4개로 주어져 있기 때문에

각각 비교해야하는 톱니바퀴의 맞물리는 부분을 보자면 다음과 같다.

 

1번 톱니바퀴 -> 2번 톱니바퀴의 3, 7 번

2번 톱니바퀴 -> 1번 톱니바퀴의 3, 3번 톱니바퀴의 7

3번 톱니바퀴 -> 2번 톱니바퀴의 2, 4번 톱니바퀴의 6

4번 톱니바퀴 -> 3번 톱니바퀴의 2

 

이제 이를 이용하여 왼쪽 , 오른쪽을 나누어 재귀를 돌려주며 

회전해야 할 톱니바퀴들을 회전해주었다.

 

# 14891 톱니바퀴
from collections import deque
import sys 

def left(num, way):
    way *= -1
    if num != 0:
        if wheels[num][6] != wheels[num-1][2]:
            left(num-1,way)
            wheels[num-1].rotate(way)
    

def right(num, way):
    way *= -1
    if num != 3:
        if wheels[num][2] != wheels[num+1][6]:
            right(num+1, way)
            wheels[num+1].rotate(way)


#main
input = sys.stdin.readline

wheels=[]

for i in range(1,5):
    wheels.append(deque(list(map(int, input().strip()))))
   
k = int(input())

for i in range(k):
    num, way = map(int, input().split())
    
    # 회전
    left(num-1, way)
    right(num-1, way)
    wheels[num-1].rotate(way)
    
#결과 계산
rst=0
cnt=1

for i in range(len(wheels)):
    if wheels[i][0] == 1:
        rst+=cnt
    cnt*=2
    
print(rst)