14891번. 톱니바퀴

http://boj.kr/14891 

한 번 명령이 주어질 때 톱니바퀴들이 연쇄적으로 어떻게 회전할지에 대해 생각해보고 그대로 만들면 된다.

톱니바퀴들을 collections의 deque로 저장해서 반시계방향 회전, 시계방향 회전을 쉽게 만들었다. (rotate)

반시계, 시계 방향이 잘 와닿지 않아서 왼쪽, 오른쪽 방향 회전이라고 대충 이름붙였다.

 

방법은 두 가지가 있다. 하나는 반복문, 하나는 재귀.

코드는 재귀가 더 깔끔해보이지만 실행시간은 완전히 똑같았다.

재귀에 익숙해지지 않는다면 좀 처음부터 와닿긴 힘들고, 반복문이 더 이해하기 쉬운 듯 하다.

 

 

 

# 반복문

각 톱니바퀴의 회전 여부(-1, 0, 1)를 담을 move 리스트를 만들고,

모든 톱니바퀴들의 회전 여부를 검사하고 난 후에 move 대로 회전한다.

import sys
from collections import deque


def calc():
    ret = 0
    for i in range(4):
        if wheel[i][0] == '1':
            ret += 1 * pow(2, i)
    return ret


def start(num, direction):
    move = [0] * 4  # 톱니바퀴들의 회전 여부를 담을 move 리스트
    move[num] = direction  # 일단 주어진 톱니바퀴는 무조건 회전

    # 왼쪽 톱니바퀴들이 회전하는지?
    next_num, next_di = num, direction  # 원본 보존을 위해 next 변수 사용 (오른쪽 톱니바퀴들도 봐야 하기 때문에)
    while 0 <= next_num-1:  # next_num-1 이 회전하는지 안하는지를 볼 것임
        if wheel[next_num][6] != wheel[next_num-1][2]:
            next_di = -next_di
            move[next_num-1] = next_di
            next_num -= 1
        else:  # 움직이지 않으면 바로 빠져나온다
            break

    # 오른쪽 톱니바퀴들이 회전하는지?
    next_num, next_di = num, direction
    while next_num+1 < 4:
        if wheel[next_num][2] != wheel[next_num+1][6]:
            next_di = -next_di
            move[next_num+1] = next_di
            next_num += 1
        else:
            break

    # move 리스트에 작성한 대로 실제로 톱니바퀴를 돌림
    for n, direction in enumerate(move):
        if direction != 0:
            wheel[n].rotate(direction)


if __name__ == '__main__':
    input = sys.stdin.readline
    wheel = [deque(input()[:-1]) for _ in range(4)]
    K = int(input())
    order = [list(map(int, input().split())) for _ in range(K)]

    for num, direction in order:
        start(num-1, direction)
    print(calc())

 

 

 

# 재귀

톱니바퀴 번호 n과 방향 di을 매개변수로 넣어 매번 move_left 함수를 호출하고

함수 내에서는 n이 아닌 n-1 이 회전하는지 확인한다. (if wheel[n][6] != wheel[n-1][2])

회전할 수 있다면 n-1 을 매개변수로 다시 move_left 함수를 호출한다.

재귀에서 돌아올 때 rotate를 실행한다. (위에서 말했듯이 n이 아닌 n-1이 회전하는지 확인했으므로, n-1을 회전시킨다)

n이 아닌 n-1 부터 회전시켰으므로 마지막으로 n을 회전시키고 프로그램을 종료한다.

(n-1 -> n+1, move_left -> move_right 동일)

import sys
from collections import deque


def calc():
    ret = 0
    for i in range(4):
        if wheel[i][0] == '1':
            ret += 1 * pow(2, i)
    return ret


def move_left(n, di):
    if n < 1:
        return
    if wheel[n][6] != wheel[n-1][2]:
        move_left(n-1, -di)
        wheel[n-1].rotate(di)


def move_right(n, di):
    if 2 < n:
        return
    if wheel[n][2] != wheel[n+1][6]:
        move_right(n+1, -di)
        wheel[n+1].rotate(di)


def start(num, direction):
    move_left(num-1, -direction)
    move_right(num-1, -direction)
    wheel[num-1].rotate(direction)


if __name__ == '__main__':
    input = sys.stdin.readline
    wheel = [deque(input()[:-1]) for _ in range(4)]
    K = int(input())  # K번의 명령어
    order = [list(map(int, input().split())) for _ in range(K)]

    for num, direction in order:
        start(num, direction)

    print(calc())