[Python] 백준 14891 : 톱니바퀴

 

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

14891번: 톱니바퀴

[풀이]
아이디어 1 : 변수명을 그림상의 톱니바퀴의 번호와 쉽게 1대1 대응 할 수 있도록 구성하자.
-  톱니 번호를 0,1,2,3,4,5,6,7 인덱스로 관리하기 보다 동서남북에 해당하는 변수를 선언한다.

-  회전명령도 G와 R로 선언해서 하드코딩을 피한다

-  톱니바퀴를 회전하는 함수를 따로 구현한다.(Rotate)

 

아이디어 2 : 연쇄적인 톱니바퀴의 회전은 큐 자료구조를 이용한다

-  이 문제의 가장 어려운 점은 톱니바퀴 회전이 연쇄적으로 일어난다는 것이다.

-  재귀로 구현하기 보다는 while문 안에서 구현을 하는것이 적절해 보인다.

-  입력으로 받은 회전 명령을 큐에 집어넣고, 이 명령에 의해 연쇄적으로 발생하는 회전 명령을 큐에 집어넣는다.
-  이 큐가 빈 큐가 될때까지 while문을 돌린다.

 

아이디어 3: 현재 수행하고 있는 회전명령이 어떤 톱니바퀴에 의해 일어났는지 체크 해야한다.
- 이러한 알고리즘을 짜지 않으면 예제입력1의 1 1 명령에서 버그가 발생한다.
- 어떠한 오류가 발생하냐면 1 1 에 의해서 2 -1 만 일어나야 하는데, 

- 이러한 2 , -1 에 의해서 다시 1 1이 발생한다. (원래는 2 ,-1 에 의해서 3 1 이 일어나야 한다.

- 2번의 회전에 영항을 준 1번 톱니바퀴가 다시 2번톱니의 회전에 의해서 회전하는거는 요구사항에 맞지 않다(만약에 N극 S극이 번갈아가면서 있는 톱니바퀴라면 무한동력이 발생할 수도 있다....) 

- 큐에 넣을 튜플의 세번째 원소에 영향을 받은 톱니바퀴 번호를 기록해서 before 변수에 저장한다.

 

[ 코드]

# 톱니 바퀴를 회전 시키는 함수
def Rotate(G,R):
    # 시계방향으로 회전
    if R == 1:
        g1 = Gear[G][0:7]
        g2 = Gear[G][-1]
        Gear[G] = [g2] + g1
    # 시계 반대방향으로 회전
    if R == -1:
        g1 = Gear[G][1:8]
        g2 = Gear[G][0]
        Gear[G] =g1+[g2]

Gear = [[] for _ in range(5)]

# 톱니바퀴의 바퀴위치를 쉽게 찾기위한 변수선언
t = 0
r = 2
b = 4
l = 6

# 입력(명령)의 종류를 쉽게 알기 위한 변수선언
G = 0 # 톱니바퀴의 번호
R = 0 # 회전 방향

# 톱니바퀴 정보 입력받기
for i in range(1,5):
    Gear[i] = list(map(int,input()))
#print('init: ',Gear)

# 회전명령을 하나씩 순회하는 for문
for i in range(int(input())):
    order = list(map(int,input().split()))
    Q = []
    Q.append((order[0],order[1],-1))

    # R이1은 시계방향 -1 은 시계반대 방향
    ## 1번 톱니바퀴
    before = -1 #어떤 톱니바퀴에 의해 연쇄 회전이 일어나게 됐는지 기록해야한다
    while Q:
        now = Q.pop(0)
        G,R = now[0] ,now[1]
        before = now[2]
        #print (G,R)
        if G == 1 :
            #1번톱니와 2번톱니의 맞닿은 극이 다를때
            if (Gear[1][r] != Gear[2][l]) and before != 2:
                Q.append((2, -R , 1))

            Rotate(G, R)

        ## 2번 톱니바퀴
        if G == 2 :
            # 2번톱니와 1번톱니의 맞닿은 극이 다를때
            if (Gear[2][l] != Gear[1][r]) and before != 1:
                Q.append((1, -R, 2))


            # 2번톱니와 3번톱니의 맞닿은 극이 다를때
            if (Gear[2][r] != Gear[3][l]) and before != 3:
                Q.append((3, -R, 2))

            Rotate(G, R)

        ## 3번 톱니바퀴
        if G == 3 :
            # 3번톱니와 2번톱니의 맞닿은 극이 다를때
            if (Gear[3][l] != Gear[2][r]) and before != 2:
                Q.append((2, -R, 3))

            # 2번톱니와 3번톱니의 맞닿은 극이 같을때
            if (Gear[3][r] != Gear[4][l]) and before != 4:
                Q.append((4, -R, 3))

            Rotate(G, R)

        ## 4번 톱니바퀴
        if G == 4 :
            #4번톱니와 3번 톱니의 맞닿은 극이 다를때
            if (Gear[4][l] != Gear[3][r]) and before != 3:
                Q.append((3, -R, 4))

            Rotate(G, R)

        #print(Gear)
        
# 점수 계산하기
ans = 0
if Gear[1][t] == 1 :
    ans += 1
if Gear[2][t] == 1 :
    ans += 2
if Gear[3][t] == 1 :
    ans += 4
if Gear[4][t] == 1 :
    ans += 8

print(ans)

 

구현문제는 Python으로 푸는게 정신건강에 좋다.