[Python] 백준 14891번 - 톱니바퀴 (재귀)

문제: https://www.acmicpc.net/problem/14891

14891번: 톱니바퀴

 

 

https://jjung0326.tistory.com/96

[Python] 백준 14891번 - 톱니바퀴

어제 하드코딩(?)으로 풀었던 문제를 재귀로 풀어보았다. (dfs가 아니었다 ㅎㅎ)

혼자 풀어보다가 잘 모르겠어서 풀이를 보고 해결했다.

몰랐는데, python rotate 함수를 쓰면 deque 내에서 자리를 간단하게 옮길 수 있었다!

 

Python deque.rotate()

deque 자료형에 대해 rotate 함수를 사용하면 자리를 쉽게 바꿀 수 있다.

함수의 인자로 양수를 양수를 주면 오른쪽으로 회전하고, 음수를 주면 왼쪽으로 회전하게 된다.

from collections import deque

test = deque([1, 2, 3, 4, 5])
test.rotate(1)
print(test)		# [5, 1, 2, 3, 4]

test.rotate(-2)
print(test)		# [2, 3, 4, 5, 1]

 

from collections import deque

gears = {}
for i in range(1, 5):
    gears[i] = deque(map(int, input()))

k = int(input())
rotation = [tuple(map(int, input().split())) for _ in range(k)]

def rotate_right(gear, dir):
    # 회전하지 않는 경우
    if gear > 4 or gears[gear-1][2] == gears[gear][6]:
        return
    
    # 회전하는 경우
    if gears[gear-1][2] != gears[gear][6]:
        rotate_right(gear+1, -dir)      # 재귀
        gears[gear].rotate(dir)
        
def rotate_left(gear, dir):
    if gear < 1 or gears[gear][2] == gears[gear+1][6]:
        return
    
    if gears[gear][2] != gears[gear+1][6]:
        rotate_left(gear-1, -dir)
        gears[gear].rotate(dir)

for i in range(k):
    gear = rotation[i][0]
    dir = rotation[i][1]
    
    rotate_right(gear+1, -dir)
    rotate_left(gear-1, -dir)
    gears[gear].rotate(dir)

answer = 0
if gears[1][0] == 1:
    answer += 1
if gears[2][0] == 1:
    answer += 2
if gears[3][0] == 1:
    answer += 4
if gears[4][0] == 1:
    answer += 8
print(answer)