문제

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

풀이

조건

• 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.
  • 4개 밖에 없다.
• 톱니바퀴를 총 K번 회전시킨다.
• 회전은 시계 방향과 반시계 방향이 있고 1이 시계방향, -1이 반시계방향이다
• 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다.
  • 연쇄적으로 회전한다.

풀이 순서

• 톱니바퀴의 상태를 Dictionary에 저장한다.
• 시계방향으로 12시 방향의 값을 deque에 넣는다.
  • 12시 방향의 값이 인덱스 0의 위치하도록 한다.
• 오른쪽과 왼쪽을 탐색하고 회전 가능하면 회전시키는 함수를 만든다.
  • 재귀를 통해 기준 톱니에서 가장 멀리 떨어진 회전 가능한 톱니까지 탐색하고 거기서부터 차례로 회전시켜나온다.
  • 인접한 톱니는 인덱스 2, 인덱스 6이다.
  • 이 때 deque.rotate(양수 or 음수) 메소드를 사용한다.
  • 위 메소드의 파라미터로 양수를 전달하면 맨 뒤의 값이 맨 앞으로 회전한다.(시계방향)
  • 위 메소드의 파라미터로 음수를 전달하면 맨 앞의 값이 맨 뒤로 회전한다.(반시계방향)
• 회전을 마친 뒤 기준 톱니를 회전시킨다.

코드

import sys
from collections import deque

# 기준 오른쪽을 탐색하고 회전
def check_right(start, dirs):
    if start > 4 or chains[start-1][2] == chains[start][6]:
        return

    if chains[start-1][2] != chains[start][6]:
        check_right(start+1, -dirs) # 가능한 가장 먼 곳 까지 갔다가
        chains[start].rotate(dirs) # 회전시킴

# 기준 왼쪽을 탐색하고 회전
def check_left(start, dirs):
    if start < 1 or chains[start][2] == chains[start+1][6]:
        return

    if chains[start+1][6] != chains[start][2]:
        check_left(start-1, -dirs) # 가능한 가장 먼 곳 까지 갔다가
        chains[start].rotate(dirs) # 회전시킴

chains = dict() # 톱니들 넣을 딕셔너리

# 입력받음
for i in range(1, 5):
    chains[i] = deque(list(map(int, list(sys.stdin.readline().replace('\n', '')))))

K = int(sys.stdin.readline())
for _ in range(K):
    
    # 톱니번호, 회전방향
    num, dirs = map(int, sys.stdin.readline().split())

    check_right(num+1, -dirs) # 기준 바로 오른쪽부터 시작
    check_left(num-1, -dirs) # 기준 바로 왼쪽부터 시작

    chains[num].rotate(dirs) # 기준 회전

result = 0
for i in range(4):
    result += (2**i) * chains[i+1][0]
print(result)

정리

• deque에 rotate() 메소드가 있다는 것을 처음 알았다.
• 기능을 함수로 빼내는 연습을 더 해야겠다.
• 재귀를 통해 톱니를 탐색하는 방법이 신기했다.