코딩테스트 스터디 - 백준 14891번: 톱니바퀴 (python)

문제

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

14891번: 톱니바퀴

요약

8개의 이빨은 가진 톱니바퀴 4개가 가로로 연결돼있다.

어떤 톱니바퀴 A를 움직이면, 연결된 B 톱니바퀴는 A와 B가 맞닿아있는 이빨의 극이 달라야 움직인다.

극이 같으면 움직이지 않으며, B와 연결된 다른 톱니도 움직이지 않는다.

톱니바퀴를 움직이는 행동을 K번 한 후 톱니바퀴들의 상태를 알아내면 된다.

의식의 흐름

우선 뭔가 최적값을 찾는 탐색 문제가 아니기 때문에 그냥 시키는 대로 구현하는 문제다.

다만 톱니가 01010011 이런식으로 2진수로 주어지기때문에, 연습겸 톱니 정보를 2진수로 저장한 뒤

쉬프트 연산을 통해 바퀴를 회전해보기로 했다.

어차피 이렇게 하는게 문자열이나 리스트를 쓰는 것보다 훨씬 빠를 것이다.

 

몇 번째 톱니바퀴를 움직이느냐에 따라 움직이는 방향을 정하는 순서가 달라지기 때문에,

이를 뭔가 하나의 식으로 표현하려고 고민해봤지만 결국 1,2,3,4번째 톱니가 움직일 때를 전부 if~else로 나눴다.

구현

자료구조

각 톱니를 이진수 숫자 하나로 저장하는 4칸짜리 리스트 gear를 만들었다.

또, 각 행동을 할 때마다 각 톱니바퀴의 회전 방향을 기록하는 dirs 리스트도 만들었다.

이 dirs 리스트는 움직인 톱니바퀴 번호에 따라 update 순서가 달라진다.

알고리즘

전반적인 알고리즘은 코드를 보는 것이 이해가 편합니다.

 

우선 두 톱니가 맞물려있는지 확인하는 link(a,b) 함수를 만들었다.

a<b를 가정하고, a의 3번째 자리와 b의 7번째 자리를 이용해 비트 연산으로 구했다.

0b00100000과 and 연산을 한 결과를 0b00100000와 == 비교를 하면, 3번째 자리가 1인지 알 수 있다.

 

다음으로, 매 행동마다 dirs를 만든다.

dirs는 우선 입력한 행동을 먼저 기록한다.

예를들어 3번째 바퀴를 반시계로 돌린다면, dirs = [0, 0, -1, 0]이 된다.

그 다음 움직인 톱니바퀴에 따라 양옆으로 차례로 확인한다.

예를들어 위의 경우, 

if link(3,4) : dirs[4] = -dirs[3]   #3번째의 반대방향으로 돌림

if link(2,3) : dirs[2]= -dirs[3]    #3번째의 반대방향으로 돌림

if link(1,2) : dirs[1] = -dirs[2]   #2번째의 반대방향으로 돌림. 만약 2번째가 안돌았다면 0이므로 link == true여도 안돌아감.

순으로 반영한다.

 

마지막으로 dirs를 확인해 각 톱니를 돌려준다.

그냥 shift를 해주면 사라지는 자리수가 있으니, 적절하게 더해준다. 

코드

비트 연산을 이용한 문제는 처음이여서, link 함수와 shift 부분이 까다로웠다.

하지만 문제자체는 어려운 문제는 아니었던 것 같다.

 

'''
    문제 출처 : https://www.acmicpc.net/problem/14891
'''

gears = []

for i in range(4):
    gears.append(int(input(),2))

left_tooth = 0b00000010
right_tooth = 0b00100000

def link(a, b): #a, b가 극이 다른지 (a < b)
    global gears
    return (gears[a] & right_tooth == right_tooth) ^ (gears[b] & left_tooth ==left_tooth)

K = int(input())
for k in range(K):
    num, dir = map(int,input().split(' '))
    dirs = [0, 0, 0, 0]
    num -= 1
    dirs[num] = dir
    if num == 0:
        for i in range(3):
            if link(i, i+1):
                dirs[i+1] = -dirs[i]
    elif num == 3:
        for i in range(3, 0, -1):
            if link(i-1, i):
                dirs[i-1] = -dirs[i]
    else:
        if link(num-1, num):
            dirs[num-1] = -dirs[num]
        if link(num, num+1):
            dirs[num+1] = -dirs[num]
        if num == 1 and link(2, 3):
            dirs[3] = -dirs[2]
        elif num == 2 and link(0, 1):
            dirs[0] = -dirs[1]
    for i in range(4):
        if dirs[i] == 1:
            gears[i] = (gears[i]%2) * (2**8) + gears[i] >> 1
        elif dirs[i] == -1:
            gears[i] = int(gears[i] / (2**7)) + (gears[i] << 1) % (2**8)

print(int(gears[0] / (2**7)) + 2*int(gears[1] / (2**7)) + 4*int(gears[2] / (2**7)) + 8*int(gears[3] / (2**7)))