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

14891번: 톱니바퀴 (acmicpc.net)

14891번: 톱니바퀴

 

문제 요약

톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다.

톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 극이 같다면 회전하지 않는다.

 

 

문제 풀이

- deque에 rotate 활용 (입력값으로 들어오는 회전 방향이 함수에서 사용하는 부분과 일치)

- 입력받은 톱니바퀴 번호를 기준으로 맞닿은 톱니 확인 (인덱스로 2, 6)

- 기준점에서 왼쪽과 오른쪽 톱니바퀴의 회전 여부를 각각 재귀적으로 탐색

 

<첫번째 issue>

index error가 발생했다. IndexError: list index out of range

# 기준 톱니바퀴에서 왼쪽 톱니바퀴 확인
def rotateL(num, dir):
    if num < 0 : return  # 가장 왼쪽 톱니바퀴까지
    if wheel[num][6] != wheel[num-1][2]:
        rotateL(num-1, -dir)
        wheel[num].rotate(dir)  # dir 방향으로 회전

# 기준 톱니바퀴에서 오른쪽 톱니바퀴 확인
def rotateR(num, dir):
    if num > 3 : return  # 가장 오른쪽 톱니바퀴까지
    if wheel[num][2] != wheel[num+1][6]:
        rotateR(num+1, -dir)    # 오른쪽 톱니바퀴 계속 확인
        wheel[num].rotate(dir)  # 회전

deque에 저장되어 있는 인덱스 범위를 초과하도록 코드를 짰기 때문에 수정해야한다.

위 코드에서는 rotateL에서는 wheel[-1], rotateR에서는 wheel[4]가 있어야하기에 오류가 났다.

num 관련 모든 코드를 다시 수정해보자

 

 

<두번째 issue>

인덱스 에러를 해결했는데 답이 틀렸다.

이유가 뭘까

from collections import deque

# 기준 톱니바퀴에서 왼쪽 톱니바퀴 확인
def rotateL(num, dir):
    if num < 0 : return  # 가장 왼쪽 톱니바퀴까지
    if wheel[num][2] != wheel[num+1][6]:
        rotateL(num-1, -dir)
        wheel[num].rotate(dir)  # dir 방향으로 회전

# 기준 톱니바퀴에서 오른쪽 톱니바퀴 확인
def rotateR(num, dir):
    if num > 3 : return  # 가장 오른쪽 톱니바퀴까지
    if wheel[num-1][2] != wheel[num][6]:
        rotateR(num+1, -dir)    # 오른쪽 톱니바퀴 계속 확인
        wheel[num].rotate(dir)  # 회전

# 톱니바퀴 0,1,2,3으로 저장
wheel = [deque(map(int, input())) for _ in range(4)]
n = int(input())

# 톱니바퀴 회전
for _ in range(n):
    wheelNum, direction = list(deque(map(int, input().split())))
    wheel[wheelNum-1].rotate(direction)  # 기준 톱니바퀴
    rotateL(wheelNum-2, -direction)       # 왼쪽 톱니바퀴
    rotateR(wheelNum, -direction)         # 오른쪽 톱니바퀴

# 점수 계산
score = 0
if wheel[0][0] == 1 : score += 1
if wheel[1][0] == 1 : score += 2
if wheel[2][0] == 1 : score += 4
if wheel[3][0] == 1 : score += 8
print(score)

톱니바퀴 회전 부분이 문제였다.

왼쪽, 오른쪽 톱니바퀴에 대한 재귀를 먼저 수행한 뒤 기준 톱니바퀴를 회전해야 한다.

기준 톱니바퀴가 먼저 돌아가면 그 상태에서 인접한 톱니바퀴의 회전 여부가 달라지기 때문에 한번의 수행에서의 상태가 달라진다.

 

 

최종 코드

from collections import deque

# 기준 톱니바퀴에서 왼쪽 톱니바퀴 확인
def rotateL(num, dir):
    if num < 0 : return  # 가장 왼쪽 톱니바퀴까지
    if wheel[num][2] != wheel[num+1][6]:
        rotateL(num-1, -dir)
        wheel[num].rotate(dir)  # dir 방향으로 회전

# 기준 톱니바퀴에서 오른쪽 톱니바퀴 확인
def rotateR(num, dir):
    if num > 3 : return  # 가장 오른쪽 톱니바퀴까지
    if wheel[num-1][2] != wheel[num][6]:
        rotateR(num+1, -dir)    # 오른쪽 톱니바퀴 계속 확인
        wheel[num].rotate(dir)  # 회전

# 톱니바퀴 0,1,2,3으로 저장
wheel = [deque(map(int, input())) for _ in range(4)]
n = int(input())

# 톱니바퀴 회전
for _ in range(n):
    wheelNum, direction = map(int, input().split())
    rotateL(wheelNum-2, -direction)       # 왼쪽 톱니바퀴
    rotateR(wheelNum, -direction)         # 오른쪽 톱니바퀴
    wheel[wheelNum - 1].rotate(direction)  # 기준 톱니바퀴

# 점수 계산
score = 0
if wheel[0][0] == 1 : score += 1
if wheel[1][0] == 1 : score += 2
if wheel[2][0] == 1 : score += 4
if wheel[3][0] == 1 : score += 8
print(score)

 

 

* 정리

wheel = [deque(map(int, input())) for _ in range(4)]
print(wheel)
print(wheel[0])

output:

[deque([1, 1]), deque([1, 2]), deque([1, 3]), deque([1, 4])]

deque([1, 1])

 

 

array = [1, 2, 3, 4, 5]
array.rotate(1)

rotate(1)의 결과 (문제 기준으로 시계 방향으로 회전한 결과)

[1, 2, 3, 4, 5] -> [5, 1, 2, 3, 4]

 

array = [1, 2, 3, 4, 5]
array.rotate(-1)

rotate(-1)의 결과 (문제 기준으로 반시계 방향으로 회전한 결과)

[1, 2, 3, 4, 5] -> [2, 3, 4, 5, 1]