[Python] 14891. 톱니바퀴(골5) / 재귀 응용 구현

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

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

14891번: 톱니바퀴

---

2. 핵심 아이디어

역대급으로 문제 아이디어가 떠오르지 않았던 문제

결국 인터넷에서 다른 사람의 아이디어를 참고하여 문제를 풀었다.

 

문제를 풀면서 가장 어려웠던 점은

고려해야할 것들이 너무 많았던 사실이다.

 

그리고 이러한 고려사안을 분할하여

재귀로 구현한 다른 이의 코드를 보고 감탄했다.

 

그럼 아이디어를 설명해보겠다.

 

2-1) rotate 메소드

먼저 코드를 구현하기 위해서는 Q를 돌리는

rotate라는 메소드를 응용하면 훨씬 편하다.

 

rotate는 말그대로 리스트를 돌리는 행위로

양수를 넣으면 오른쪽으로 / 음수를 넣으면 왼쪽을로 회전한다.

 

예를 들어

from collections import deque

q= deque([1,2,3])

result1 = q.rotate(1)  # 3, 1, 2
result2 = q.rotate(1)  # 2, 3, 1
result3 = q.rotate(1)  # 1, 2, 3

result4 = q.rotate(-1) # 2, 3, 1
result5 = q.rotate(-1) # 3, 1, 2
result6 = q.rotate(-1) # 1, 2, 3

 

이런식이다.

 

2-2) 재귀함수 구현

 

그럼 문제로 돌아와 톱니바퀴를 돌리는 상황을 고려해보자

 

내가 3번째 톱니바퀴를 돌린다면 고려사안은 다음과 같다.

 

1) 돌리는 톱니바퀴 왼쪽 = 2번째 톱니바퀴

=> 서로 맞닿는 부분이 다른 극이면 돌림 / 아니면 그대로

 

2) 돌리는 톱니바퀴 오른쪽 = 4번째 톱니바퀴

=> 서로 맞닿는 부분이 다른 극이면 돌림 / 아니면 그대로

 

3) 3번째 톱니바퀴를 돌린다.

 

그리고 이 왼쪽으로 전달된 힘은 어떤 톱니바퀴가 멈추거나 범위를 벗어날때까지 계속 전달된다.

마찬가지로 오른쪽으로 전달된 힘은 어떤 톱니바퀴가 멈추거나 범위를 벗어날때까지 계속된다

 

그럼 먼저 첫번째 -> 돌리는 바퀴 기준 왼쪽돌리는 톱니바퀴의 왼쪽 톱니바퀴를 기준으로 생각해보자

#왼쪽 돌리기
def rotate_left(x, d):
  if x<1 or gear[x][2]==gear[x+1][6]:
    return
  
  rotate_left(x-1, -d)
  gear[x].rotate(d)

왼쪽 톱니바퀴 번호를 x라 할 때

x가 멈추는 조건은

1) 범위를 벗어남 => 톱니바퀴 번호(x) <02) 서로 맞닿는 극이 같음 => gear[x][2]== gear[x+1][6] (돌리는 바퀴)

 

만약 x를 돌려야 한다면이 힘을 먼저 자신의 왼쪽 톱니바퀴(x-1)에 반대방향으로 전달하고 => rotate_left(x-1, -d)톱니바퀴를 돌린다. => gear[x].rotate(d)

 

돌리는 톱니바퀴 기준으로

오른쪽 톱니바퀴도 마찬가지이다.

#오른쪽 확인
def rotate_right(x, d):
  if x>4 or gear[x-1][2]==gear[x][6]:
    return
  
  #힘을 오른쪽으로 전달
  rotate_right(x+1, -d)
  gear[x].rotate(d)

 

오른쪽 톱니바퀴 번호를 x라 할 때

x가 멈추는 조건은

1) 범위를 벗어남 => 톱니바퀴 번호(x) >4

2) 서로 맞닿는 극이 같음 => gear[x][6]== gear[x-1][2] (돌리는 바퀴)

 

만약 x를 돌려야 한다면

이 힘을 자신의 오른쪽에게 반대방향으로 전달하고 => rotate_right(x+1, -d)

톱니바퀴를 돌린다. gear[x].rotate(d)

 

 

2-2) main함수 구현

 

이제 모든 것이 준비되었다.

#재귀함수 응용
gear={}

for i in range(1, 5):
  gear[i]= deque(map(int, input()))

각 gear를 리스트로 저장하고

번호를 부르면 리스트가 나올 수 있게 사전에 저장해준다.

#재귀함수 응용
for _ in range(n):
  x,d= map(int, input().split())
  rotate_right(x+1, -d)
  rotate_left(x-1, -d)
  gear[x].rotate(d)

이후 돌리는 번호가 나오면

돌리는 번호 왼쪽에 반대방향으로 힘을 전달하고 => rotate_left(x-1,-d)

돌리는 번호 오른쪽에 반대방향으로 힘을 전달한다. => rotate_right(x+1, -d)

그리고 톱니바퀴를 돌린다. => gear[x].rotate(d)

 

이것을 반복하고 점수를 출력하면

답이 나온다.

 

 

---

3. 코드

from collections import deque

#오른쪽 확인
def rotate_right(x, d):
  if x>4 or gear[x-1][2]==gear[x][6]:
    return
  
  #힘을 오른쪽으로 전달
  rotate_right(x+1, -d)
  gear[x].rotate(d)

#왼쪽 돌리기
def rotate_left(x, d):
  if x<1 or gear[x][2]==gear[x+1][6]:
    return
  
  rotate_left(x-1, -d)
  gear[x].rotate(d)


#재귀함수 응용
gear={}

for i in range(1, 5):
  gear[i]= deque(map(int, input()))

n= int(input())

for _ in range(n):
  x,d= map(int, input().split())
  rotate_right(x+1, -d)
  rotate_left(x-1, -d)
  gear[x].rotate(d)

result=0
for i in range(4):
  result+=gear[i+1][0]*(2**i)

print(result)

---

4.배운점

다른 구현문제보다 재귀적 사고로 문제를 바라보기 힘들다는 점을 극명하게 느끼게 해준문제

4개로 톱니바퀴가 제한되어 있어 모든 케이스를 세분화하여 함수를 만들고 구현해보았지만 

결국 통과하지 못했다.

 

무언가를 반복적으로 고려해야주어야 할 땐 재귀라는 키워드를 마음 깊은 곳에서 꺼내보자

 

>>연관 문제

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

15662번: 톱니바퀴 (2)