[python]백준 14891번: 톱니바퀴

문제

www.acmicpc.net/problem/14891

14891번: 톱니바퀴

 

아이디어

구현 테마인데, 톱니바퀴를 연달아 반대방향으로 돌리는지 확인하고 돌리는 함수 do_wheels 를 만들어, 재귀형태로 풀었다. 바퀴는 4개로 고정이라서 depth가 아무리 깊어봤자 최대 2다.

 

4개의 톱니바퀴의 왼쪽부분과 오른쪽 부분을 상수 LEFT,RIGHT = 6,2 로 위치를 지정해놓고, 인덱스에는 변화를 주지않은채 '돌리는행동'을 queue의 앞과 끝을 pop,append 해주는 식으로 정의했다.

 

그래서 deque 자료구조를 통해 시계방향은 popright후 그 값을 appendleft 했고 반시계방향은 popleft 후 appendright 했다.

 

코드

from collections import deque
from sys import stdin

wheels = []
visited = [False]*4
LEFT, RIGHT = 6,2
for i in range(4):
    w = input().rstrip()
    wheels.append(deque())
    for idx in range(len(w)):
        wheels[i].append(int(w[idx]))

K = int(input())


def roll_wheel(wheels, index, dir):
    var = 0
    if dir == -1:
        var = wheels[index].popleft()
        wheels[index].append(var)
    else:
        var = wheels[index].pop()
        wheels[index].appendleft(var)
    return


def do_wheels(wheels, start, dir, visited):
    if not visited[start]:
        l = wheels[start][LEFT]
        r = wheels[start][RIGHT]
        roll_wheel(wheels, start, dir)
        visited[start] = True
        if start != 0:
            if l != wheels[start-1][RIGHT] and not visited[start-1]:
                do_wheels(wheels,start-1,-dir,visited)
        if start != 3:
            if r != wheels[start+1][LEFT] and not visited[start+1]:
                do_wheels(wheels,start+1,-dir,visited)
    visited[start] = False

for k in range(K):
    start, dir = map(int, stdin.readline().split())
    do_wheels(wheels, start-1, dir, visited)

ans = 0
score = [1,2,4,8]
for j in range(4):
    if wheels[j][0] == 1:
        ans += score[j]

print(ans)

오답이 한번 났는데, visited 의 조건을 다음 위치로의 재귀함수가 실행되기 위한 조건으로 추가했더니 해결되었다.

 

진입 후에 visited 체크를 하지말고 진입하기 전에 visited 인지를 체크해주는게 더 나은 방식인가보다. (차이를 잘 모르겠음)