백준 14891 : 톱니바퀴(파이썬)

https://www.acmicpc.net/problem/14891

14891번: 톱니바퀴

문제는 위와 같다.

 

문제의 포인트는 기어를 돌리면서 인덱스 정보를 바꿔주는 것과,

처음 회전하는 기어를 기준으로 양 옆의 회전여부를 결정하는 것이다.

 

 1. 기어 회전

 시계방향과 반시계 방향에 따라 작동할 수 있도록 해줘야한다.

 반복문을 이용해서 바꿀 수 있지만 파이썬 리스트의 기본함수를 이용해서 구성했다. 

 insert, append, del을 적절히 이용하면 기어의 회전 결과를 구현할 수 있다.

예를 들어, 12시 기준으로 인덱스 정보가 시계방향으로 구성되어 있고, 이것을 시계방향으로 회전시킨다면 오른쪽과 같은 숫자가 한칸씩 시계방향으로 움직인 형태가 될 것이다. 기어의 인덱스 마지막 인덱스 정보를 맨 앞에 삽입 시켜주고, 맨 마지막 인덱스를 지워주면 시계방향으로 회전한 효과가 나온다. 반시계 방향으로 회전하는 것도 마찬가지 원리로 생각하면 구성하기 쉽다. 이를 함수로 만들어서 활용했다.

def turn(n, d) :
    if d == 1 : # 시계 방향
        gear[n].insert(0, gear[n][-1])
        del gear[n][-1]
    else : # 반시계 방향
        gear[n].append(gear[n][0])
        del gear[n][0]

 2. 첫 번째 기어 회전 이후 양 옆의 기어 회전 여부 판단

첫 번째 기어가 회전하고 그 다음 옆의 기어가 회전하는 경우는 첫 번째 기어가 회전하기 전의 극 정보와 맞물려있는 그 다음 기어의 극 정보와 비교해야한다. 일반화 시켜보면,

 

n 번째 기어 회전 + 회전 이전의 극 정보 저장 -> n-1 번째 기어와 n+1 번째 기어와 맞닿아 있는 극정보 확인

 

그리고 나서, 회전할 수 있다면 n번째 기어가 회전한 것과 반대방향으로 회전하면 된다. 이를 재귀함수로 구성하였다. 이렇게 하면 반드시 확인해야 하는 것이 이미 회전한 기어는 다시 회전하지 않도록 해야한다. 왜냐하면 n-1 번째 기어 입장에서는 n번째 기어도 참조를 하게 되기 때문이다. 

def activate(n, l, r, d, gear_info) :
    # l, r 은 이미 돌아간 톱니의 회전 이전의 오른쪽 왼쪽 정보
    if n < 0 : return False
    if n >= 4 : return False
    nl, nr = gear[n][6], gear[n][2]
    # 이전 기어의 정보에 대해서 오른쪽인지 왼쪽인지 정보가 필요함
    if gear_info == -1 : # 이전 기어가 현재 기어에 대해 오른쪽에 있음
        pole = nr - l
    elif gear_info == 1 : # 이전 기어가 현재 기어에 대해 왼쪽에 있음
        pole = nl - r
    if pole == 0 : return False # 극성이 같으면 회전 멈춤
    else : 
        # 시계 면 반시계, 반시계면 시계
        d *= -1
        if not active[n] :
            turn(n, d)
            active[n] = True
            activate(n-1, nl, nr, d, -1)
            activate(n+1, nl, nr, d, 1)
    return False

 

 3. 전체 코드

 메모리 123316kb / 시간 112 ms

# 기어 톱니의 정보
gear = [list(map(int, input().strip())) for _ in range(4)]
# 회전 횟수
k = int(input())
# 회전할 톱니 / 방향 정보
info = [list(map(int, input().split())) for _ in range(k)]

def turn(n, d) :
    if d == 1 : # 시계 방향
        gear[n].insert(0, gear[n][-1])
        del gear[n][-1]
    else : # 반시계 방향
        gear[n].append(gear[n][0])
        del gear[n][0]

def activate(n, l, r, d, gear_info) :
    # l, r 은 이미 돌아간 톱니의 회전 이전의 오른쪽 왼쪽 정보
    if n < 0 : return False
    if n >= 4 : return False
    nl, nr = gear[n][6], gear[n][2]
    # 이전 기어의 정보에 대해서 오른쪽인지 왼쪽인지 정보가 필요함
    if gear_info == -1 : # 이전 기어가 현재 기어에 대해 오른쪽에 있음
        pole = nr - l
    elif gear_info == 1 : # 이전 기어가 현재 기어에 대해 왼쪽에 있음
        pole = nl - r
    if pole == 0 : return False # 극성이 같으면 회전 멈춤
    else : 
        # 시계 면 반시계, 반시계면 시계
        d *= -1
        if not active[n] :
            turn(n, d)
            active[n] = True
            activate(n-1, nl, nr, d, -1)
            activate(n+1, nl, nr, d, 1)
    return False

for i in range(k) :
    active = [False] * 4
    # 첫 기어 돌려돌려 돌림판
    n, d = info[i][0] -1, info[i][1]
    # print(n, gear)
    l, r = gear[n][6], gear[n][2]
    active[n] = True
    turn(n, d)
    activate(n-1, l, r, d, -1)
    activate(n + 1, l, r, d, +1)

result = 0
score = [1, 2, 4, 8]
for i in range(4) :
    if gear[i][0] != 0 :
        result += score[i]

print(result)