[백준/Python(파이썬)] 14891_톱니바퀴

문제가 너무 길고 그림이 많은 관계로 링크로 대체합니다.

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

14891번: 톱니바퀴

---

총 4개의 톱니바퀴가 존재하고, 각각의 톱니바퀴 칸마다 N극(0)과 S극(1)이 적혀있다.

톱니바퀴를 K번 회전시키려고 할 때, 서로 맞닿은 극에 따라서 인접한 톱니바퀴를 회전시킬 수 있다.

K번 회전이 끝난 후 12시 방향에 위치한 톱니바퀴의 칸이 N극이냐 S극이냐에 따라서 점수를 매기고 최종 결과를 출력한다.

이 문제는 먼저 인접한 톱니바퀴가 회전하는지에 대한 유무를 파악한 후 회전시키는 것이 포인트다.

문제의 흐름을 보면 다음과 같다.

 

1. 회전시킬 톱니바퀴의 번호 (number), 회전시킬 방향(direction)을 입력한다.
2. 회전시킬 톱니바퀴의 오른쪽에 위치한 톱니바퀴들이 맞닿은 부분들을 검사한다.
3. 인접한 두 부분이 다르다면 오른쪽에 위치한 톱니바퀴를 회전시킨다.
4. 인접한 두 부분이 같거나 톱니바퀴에 끝에 위치하게 되면 종료한다.
5. 2~3번 부분을 왼쪽에 인접한 톱니바퀴로 기준을 바꾸어 실행한다.
6. 왼쪽과 오른쪽이 모두 완료되었으면 처음 회전시킬 톱니바퀴를 회전시킨다.
7. K번 회전이 끝나면 점수를 계산하고 출력한다.

해당 문제를 풀면서 주의할 점이 있는데, 주의점은 다음과 같다.

 

• 톱니바퀴의 인접한 곳을 확인하는 인덱스는 12시(index : 0)기준으로 Index : 2 (3시)와 Index : 6 (9시)이다. 
• 인접한 곳이 움직이지 않더라도 기준이 되는 톱니바퀴는 회전한다.
• 서로 인접하는 톱니바퀴는 반대로 회전한다.

시계방향은 1, 반시계방향은 0으로 판단하는데, 이 부분이 파이썬으로 작업할 때 굉장히 편리한 부분 중 하나다.

파이썬에서 deque에 rotate()라는 함수를 이용해서 리스트를 회전시킬 수 있기 때문이다. 양수일 경우 오른쪽으로 회전, 음수일 경우 왼쪽으로 회전한다.

전체 코드를 보면서 어떻게 구현했는지 확인해보자.

 

from collections import deque

def rotate_right(number, direction, Gears) :
    if number == 4 :
        return

    if Gears[number-1][2] != Gears[number][6] :
        rotate_right(number + 1, -direction, Gears)
        Gears[number].rotate(direction)
    else :
        return

def rotate_left(number,direction, Gears) :
    if number == -1 :
        return

    if Gears[number + 1][6] != Gears[number][2] :
        rotate_left(number - 1, -direction, Gears)
        Gears[number].rotate(direction)
    else :
        return

if __name__ == "__main__" :
    Gears=[]
    answer = 0
    for _ in range(4) :
        gear = input()
        li = []
        for a in gear :
            li.append(int(a))
        Gears.append(deque(li))

    N = int(input())
    for _ in range(N) :
        number, direction = map(int,input().split())
        rotate_right(number, -direction, Gears)
        rotate_left(number-2, -direction, Gears)
        Gears[number-1].rotate(direction)

    for i in range(4) :
        answer += (2**i)*Gears[i][0]
    print(answer)

 

rotate_right()와 rotate_left()는 인접한 톱니바퀴가 회전하는지 안 하는지 판단한 후 회전할 경우 회전하기 전 그다음 인접한 톱니바퀴를 확인한다. (그렇지 않으면 이미 회전한 상태로 인접한 톱니바퀴를 맞이하기 때문에 제대로 작동하지 않는다.)

 

---

요즘 토익하느라 블로그에 영 신경을 못 썼는데, 가끔씩 알고리즘을 올리니까 나름 리프레시도 되는 것 같다.

근데 안드로이드 언제 올리지....