[python] BOJ 백준 14891: 톱니바퀴

1. 문제  

총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.

이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다.

톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 

톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.

2. 입력   

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.

다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

3. 출력   

총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.

• 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
• 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
• 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
• 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

4. 해결방법   

삼성에서 자주 출제되는 구현문제이다. 톱니바퀴의 왼쪽과 오른쪽을 탐색하면서 극이 일치하는지 일치하지 않는지를 판단해주면된다. 다만, 톱니바퀴를 회전하는 부분에서는 파이썬의 deque모델을 써야한다. 다른 방법도 있겠지만, 이 방법이 제일 쉬운방법이다. deque에서는 rotate함수를 지원하여 시계방향과 반시계방향으로 회전이 가능하다. 본 문제를 구현할때는 왼쪽방향과 오른쪽 방향을 모두 조사하여야한다. 물론 제일 끝에있는 톱니바퀴들은 한방향만 조사하면된다. 이를 위해서 왼쪽방향을 탐색하는 함수와 오른쪽방향을 탐색하는 함수를 각각 따로 만들어주었다. 탐색하는 함수에서는 만약 극이 일치하지 않는다면 톱니바퀴를 회전시키고 계속해서 옆에 있는 톱니바퀴를 재귀를 활용하여 탐색해주고 끝에 다다르면 멈추어준다.  

 

5) 구현코드   

import collections
s = [] #톱니바퀴배열 
for _ in range(4):
    s.append(collections.deque(list(input())))
K = int(input()) #회전횟수
R = [list(map(int, input().split())) for _ in range(K)] 

#왼쪽 톱니바퀴 확인
def left(num, direction): 
    if num < 0: #첫번째톱는 확인안함
        return 
    if s[num][2] != s[num+1][6]: #극이 다른경우
        left(num-1, -direction)  #그 왼쪽 톱니바퀴도 조사 
        s[num].rotate(direction) #현재 톱니바퀴는 회전 

#오른쪽 톱니바퀴 확인
def right(num, direction): 
    if num > 3: #마지막은 확인안함
        return 
    if s[num][6] != s[num-1][2]: #극이 다른경우
        right(num+1, -direction) #그 오른족 톱니바퀴도 조사
        s[num].rotate(direction) #현재 톱니바퀴는 회전


for i in range(K): 
    num = R[i][0] - 1 #돌아가는 톱니바퀴
    direction = R[i][1] #시계, 반시계방향
    left(num-1, -direction) #왼쪽조사
    right(num+1, -direction) #오른쪽조사
    s[num].rotate(direction) #현재 톱니바퀴는 회전

res = 0 #점수

if s[0][0] == '1':
    res += 1
if s[1][0] == '1':
    res += 2
if s[2][0] == '1':
    res += 4
if s[3][0] == '1':
    res += 8
    
print(res)

 

⭐️난이도:  골드 5 ⭐️ 

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

14891번: 톱니바퀴