14891번 - 톱니바퀴

문제

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

14891번: 톱니바퀴

풀이 1

문제를 잘 읽어보면, 회전을 하기전에 먼저 인접 톱니들이 받는 영향을 고려해야함을 알 수 있다. 따라서 이 문제는 재귀함수로 접근하면 쉽게 풀린다는 점을 알 수 있다. 또한, 톱니를 회전하는 것은 deque 를 이용하면 매우 쉽게 구현 가능하다.

from collections import deque

sawtooth = []
for _ in range(4):
    sawtooth.append(deque(map(int,input())))
k = int(input())
rotations = []
for _ in range(k):
    rotations.append(list(map(int,input().split())))
visited = set()


def rotate(idx,direction):
    visited.add(idx)
    left,right = idx-1,idx+1
    if left >= 0 and not left in visited and sawtooth[left][2] != sawtooth[idx][6]:
        rotate(left, -direction)
    if right < 4 and not right in visited and sawtooth[right][6] != sawtooth[idx][2]:
        rotate(right, -direction)
    sawtooth[idx].rotate(direction)


for num,direction in rotations:
    rotate(num-1,direction)
    visited.clear()

answer = 0
for i in range(4):
    answer += sawtooth[i][0]*(2**i)

print(answer)

풀이 2

톱니 끼리의 상호작용은 단순한 DFS 혹은 BFS 로 해석 가능하다. 톱니바퀴 간 상호작용은 회전하기 이전 상태를 참조하므로, 재귀 호출 뒤에 톱니를 회전시켜야한다.

from collections import deque

gears = [deque()]
# 12시 방향부터, 2가 오른쪽, 6이 왼쪽
for _ in range(4):
    gears.append(deque(map(int,input())))
K = int(input())


def update_gears(idx,visited,dir):
    visited.add(idx)
    left, right = idx - 1, idx + 1
    # 왼쪽
    if left > 0 and not left in visited and gears[idx][6] != gears[left][2]:
        update_gears(left,visited,-dir)
    if right < 5 and not right in visited and gears[idx][2] != gears[right][6]:
        update_gears(right,visited,-dir)
    gears[idx].rotate(dir)


for _ in range(K):
    idx,dir = map(int,input().split())
    update_gears(idx,set(),dir)

answer = 0
for i in range(4):
    answer += 2**i if gears[i+1][0] == 1 else 0
print(answer)