Algorithm
백준
Python
톱니 바퀴

톱니바퀴 14891 문제 풀이

문제 링크 (opens in a new tab)

내 풀이

from collections import deque
 
wheel = deque()
 
for _ in range(4) :
  tmp = deque(map(int,input()))
  wheel.append(tmp)
 
cycle_cnt = int(input())
cycle = []
for _ in range(cycle_cnt) :
  cycle.append(list(map(int, input().split())))
visited = [False for _ in range(4)]
def rotate(idx, d) :
  visited[idx] = True
  if 0 < idx : # 맨 왼쪽에 있는게 아니라면
    # 왼쪽의 2시방향과 나의 6시 방향을 비교해서 다르면
    if wheel[idx - 1][2] != wheel[idx][6] :
      if not visited[idx - 1] :
        rotate(idx - 1, d * -1)
  if idx < 3 :
    if wheel[idx + 1][6] != wheel[idx][2] :
      if not visited[idx + 1] :
        rotate(idx + 1, d * -1)
 
  if d == 1 :
    wheel[idx].appendleft(wheel[idx].pop())
  else :
    wheel[idx].append(wheel[idx].popleft())
 
for c in cycle :
  visited = [False for _ in range(4)]
  rotate(c[0] - 1, c[1])
 
cnt = 0
for i in range(4) :
  if wheel[i][0] == 1 :
    cnt += 2 ** i
 
print(cnt)

다른 사람 풀이

rotate라는 함수가 있는걸 처음 알았다.
양수는 시계 방향 회전, 음수는 반시계 방향 회전을 하고 2를 넣으면 2칸만큼 회전 4를 넣으면 4칸만큼 회전한다.
시간 복잡도는 O(n)이며, n은 회전할 개수를 의미한다.

from collections import deque
def right(idx, d): # 오른쪽 톱니바퀴 확인
    # 마지막 톱니는 확인 안함
    if idx > 3:
        return
    # 같은 극이 아니면 회전
    if sawtooth[idx - 1][2] != sawtooth[idx][6]:
        right(idx + 1, -d)
        sawtooth[idx].rotate(d)
 
 
def left(idx, d):
    # 첫번째 톱니는 확인하지 않음
    if idx < 0:
        return
    # 같은 극이 아니면 회전
    if sawtooth[idx][2] != sawtooth[idx + 1][6]:
        left(idx - 1, -d)
        sawtooth[idx].rotate(d)
 
 
# 톱니바퀴 4개 입력받기
sawtooth = [deque(list(map(int, input()))) for _ in range(4)]
k = int(input())   # 회전 횟수
 
for _ in range(k):
    # 회전 정보(회전 톱니 번호 인덱스, 회전 방향) 입력받기
    idx, d = map(int, input().split())
    idx -= 1
    # 회전할 톱니 번호의 시계방향, 반시계방향이 회전 가능한지 확인하고 회전한다
    # -d인 이유는 회전할 톱니번호가 회전하는 방향의 반대방향으로 회전해야 하기 때문
    left(idx - 1, -d)
    right(idx + 1, -d)
 
    # 회전할 톱니 번호의 톱니도 회전
    sawtooth[idx].rotate(d)
 
 
# 점수 계산하여 출력
score = 0
for i in range(4):
    if sawtooth[i][0] == 1:
        score += 2 ** i
 
print(score)

Reference