[BOJ] 14891. 톱니바퀴

문제

톱니바퀴 (https://www.acmicpc.net/problem/14891)

풀이

1. 초기 접근

• 문제조건 해석
  • 각 스텝에 따라, 기존 자료구조의 값이 바뀌는데, 바뀌는게 연쇄적이다.
    • 시뮬레이션 + DFS 문제다.
• 알고리즘
  • 문제 조건에서, 많은걸 알려주는데, 일단 톱니바퀴를 리스트로 표현할 수 있음을 알 수 있다.
  • 그리고 톱니바퀴의 회전은 리스트 요소들을 왼쪽 혹은 오른쪽으로 시프트하는 것임을 알 수 있다.
    • deque 의 .rotate() 가 있다!
  • 회전 조건은, 정해진 인덱스를 비교하면 된다.
• 코드

from collections import deque
from sys import setrecursionlimit

setrecursionlimit(10**8)

def dfs(no, di, visited):
    visited.add(no)
    # 오른쪽 회전
    if no+1 <= 3 and tobs[no][2] != tobs[no+1][6] and no+1 not in visited:
        dfs(no+1, di * (-1), visited)
    # 왼쪽 회전
    if no-1 >= 0 and tobs[no][6] != tobs[no-1][2] and no-1 not in visited:
        dfs(no-1, di * (-1), visited)
    # 나 회전
    tobs[no].rotate(di)

tobs = [deque(list(input())) for _ in range(4)]

tc = int(input())
for t in range(tc):
    no, di = list(map(int, input().split()))

    dfs(no-1, di, set())

answer = 0
for i, tob in enumerate(tobs):
    if tob[0] == '1':
        answer += 1<<i
print(answer)