[Python] 백준 14891번 - 톱니바퀴

📖 문제

14891번: 톱니바퀴

 

🔎 풀이

백준 삼성 SW 역량 테스트 기출 문제집에 있는 구현 문제입니다. 풀이는 아래와 같은 과정으로 진행하였습니다.

1. 주어진 K개의 회전 방법을, 순서대로 (번호와 방향을) 꺼낸다.
2. 리스트(deque)를 만들어 번호와 방향을 넣는다.
3. 리스트에서 번호와 방향을 하나씩 뽑아 아래의 과정을 반복한다.
4. 해당 톱니바퀴를 기준으로 좌우 톱니바퀴가 존재하는지, 존재한다면 맞닿아 있는 부분이 같은 극인지 확인한다.
5. 현재 바퀴를 회전시키고, 만약 다른 극을 가지고 있었다면, 리스트에 새로운 번호와 방향을 넣는다.

주의할 점은 회전시키기 전에 옆의 톱니바퀴가 같은 극인지, 다른 극인지 확인해야 한다는 것입니다.

 

💻 코드

from collections import deque

wheel = [[]]
for _ in range(4):
    wheel.append(deque([int(x) for x in input()]))

K = int(input())
q = deque()
for _ in range(K):
    num, direct = map(int, input().split())
    q.append((num, direct))

# 옆에 톱니바퀴가 없다면 -1
side = [[-1, 2], [1, 3], [2, 4], [3, -1]]
cnt = 0
while q:
    check = [0 for _ in range(5)]
    seq = deque()
    seq.append((q.popleft()))

    while seq:
        num, direct = seq.popleft()
        left, right = side[num-1]
        # 좌우 톱니바퀴를 연달아 회전시키는지에 대한 flag
        left_flag, right_flag = 0, 0
        check[num] = 1

        # 좌우에 톱니바퀴가 존재하고 이미 회전시키지 않았으며 다른 극인 경우
        if left != -1 and not check[num-1] and wheel[left][2] != wheel[num][6]:
            left_flag = 1
        if right != -1 and not check[num+1] and wheel[right][6] != wheel[num][2]:
            right_flag = 1

        # 시계 방향, 반시계 방향으로 회전
        if direct == 1:
            k = wheel[num].pop()
            wheel[num].appendleft(k)
        if direct == -1:
            k = wheel[num].popleft()
            wheel[num].append(k)

        # 이전에 조건을 만족한 경우 옆의 톱니바퀴도 큐에 추가
        if left_flag:
            seq.append((num-1, -1 if direct == 1 else 1))
        if right_flag:
            seq.append((num+1, -1 if direct == 1 else 1))

# 최종 점수 계산
for i in range(4):
    if wheel[i+1][0]:
        cnt += 2 ** i

print(cnt)