[알고리즘] 톱니바퀴 14891 파이썬 풀이

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

1. 문제 분석

문제에서 설명한 내용을 바탕으로 사실관계를 적습니다.

-1 반시계, 1 시계 방향

리스트 1,2,3,4 를 회전할 때, 바뀐 모양을 찾아야 한다.

출력. 1번 12시 방향이 N극이면 0, S극 1

출력. 2번 12시 방향이 N극이면 0, S극 2

출력. 3번 12시 방향이 N극이면 0, S극 4

출력. 4번 12시 방향이 N극이면 0, S극 8

각각을 배열로 선언해서 값을 이동시킨다.

12시 방향부터 시계 방향으로 값이 주어진다.

2. 문제 풀이 전략

a) 톱니바퀴가 4개밖에 없으므로 각각의 경우에 따라서 if else 문을 통해서 푼다.

b) 하나의 톱니바퀴를 바꾸고 주변의 톱니바퀴에 영향을 준다.

두 가지 아이디어가 떠올랐는데, 저는 두 번째를 사용했습니다. 이 방법이 훨씬 직관적이고 첫 번째 방법은 간지가 나지 않기 때문입니다.

3. 구현

1. Recursive하게 풀 경우, 선택된 톱니바퀴가 회전 여부를 결정했는지 확인해야 합니다. 그렇지 않는다면 무한반복하게 됩니다.

2. 하나의 톱니바퀴를 처리하면 좌우의 톱니바퀴의 조건을 파악하고 참일 경우 회전시킵니다.

import sys
 
def rotate(cur, direction):
    # 2, 6번 값에 의해서 변형이 일어난다. 리스트를 회전하기 전에 값을 먼저 저장해둔다. 
    if not checked[cur]:
        checked[cur] =True
        left_value = C_list[cur][6]
        right_value = C_list[cur][2]
        #  Initial    : - 1 0 1 0 1 1 1 1 
        #  Clock-wise :   - 1 0 1 0 1 1 1 1 
        #  Counter    : 1 0 1 0 1 1 1 1 
 
        # 회전
        if direction ==1:
            temp = C_list[cur][7]
            for i in range(6,-1,-1):
                C_list[cur][i+1] = C_list[cur][i]
            C_list[cur][0]  = temp
        else:
            temp = C_list[cur][0]
            for i in range(7):
                C_list[cur][i] = C_list[cur][i+1]
            C_list[cur][7]  = temp
        
        #전이
        if cur-1>=0 and left_value != C_list[cur-1][2]:
            rotate(cur-1, -direction)
        if cur+1<=3 and right_value != C_list[cur+1][6]:
            rotate(cur+1, -direction)
        
 
C_list = [None]*4 
C_list[0]= list(sys.stdin.readline().strip())
C_list[1]= list(sys.stdin.readline().strip())
C_list[2]= list(sys.stdin.readline().strip())
C_list[3]= list(sys.stdin.readline().strip())
 
K = int(sys.stdin.readline().strip())
for i in range(K):
    checked= [False]*4
    C, direction = map(int, sys.stdin.readline().strip().split())
    rotate(C-1, direction)
count = 0
for i in range(4):
    if C_list[i][0]=='1':
        count += (2**i)
print(count)