백준 - 톱니바퀴 (삼성 기출) / Gold 5 / 14891번

문제 📋

백준 - 톱니바퀴

풀이 📝

import sys


gears = [list(map(int, sys.stdin.readline()[:-1])) for i in range(4)]
rotates_num = int(sys.stdin.readline())
rotates = [list(map(int, sys.stdin.readline().split())) for i in range(rotates_num)]


def rotate(gear_num, direction, rotated):
    if rotated[gear_num] == 1:  # 한번의 시퀀스에서 이미 돌아간 톱니는 제외.
        return

    rotated[gear_num] = 1  # 톱니 돌아간거 체크.

    if 0 < gear_num <= 3:  # 대상 톱니의 왼쪽 톱니바퀴
        left = gear_num - 1
        if gears[gear_num][6] != gears[left][2]:  # 극이 다르면 반대방향으로 돌림.
            rotate(left, -direction, rotated)
    if 0 <= gear_num < 3:  # 대상 톱니의 오른쪽 톱니바퀴
        right = gear_num + 1
        if gears[gear_num][2] != gears[right][6]:  # 극이 다르면 반대방향으로 돌림.
            rotate(right, -direction, rotated)

    if direction == 1:  # 시계 방향 또는 반시계 방향으로 회전.
        temp1 = gears[gear_num][-1]
        for i in range(len(gears[0])):
            temp2 = gears[gear_num][i]
            gears[gear_num][i] = temp1
            temp1 = temp2
    else:
        temp1 = gears[gear_num][0]
        for i in range(len(gears[0]) - 1, -1, -1):
            temp2 = gears[gear_num][i]
            gears[gear_num][i] = temp1
            temp1 = temp2
    return


for i in rotates:
    rotated_flag = [0, 0, 0, 0]
    rotate(i[0]-1, i[1], rotated_flag)

print(sum([pow(2, ((i+1) * gears[i][0])) // 2 for i in range(4)]))

꽤 어려운 문제였으며 푸는데 시간이 오래걸렸다.
이 문제의 핵심은 다음과 같다.

• 톱니를 하나 돌리면 주위 톱니들도 조건에 따라 돌기 때문에 재귀 함수를 통해서 구현해야한다.

• 한번의 시퀀스내에서 톱니는 한번만 돌아야한다. 즉, 이미 돈 톱니는 체크해줘야 한다.