14891: 톱니바퀴

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

14891번: 톱니바퀴

설명

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

• 톱니바퀴를 총 K번 회전시킨다.
• 방향은 시계 방향과 반시계 방향이 있다.
• 톱니바퀴를 회전시키기 위해서는 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야한다. 
• 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수 있고, 아닐 수 있다. 예를들어, 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면 B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 

두 톱니바퀴의 맞닿은 부분은 초록색 점선으로 묶여있는 부분이다. 여기서, 3번 톱니바퀴를 반시계 방향으로 회전했다면, 4번 톱니바퀴는 시계 방향으로 회전하게 된다. 2번 톱니바퀴는 맞닿은 부분이 S극으로 서로 같기 때문에, 회전하지 않게 되고, 1번 톱니바퀴는 2번이 회전하지 않았기 때문에, 회전하지 않게 된다. 따라서, 아래 그림과 같은 모양을 만들게 된다.

위와 같은 상태에서 1번 톱니바퀴를 시계 방향으로 회전시키면, 2번 톱니바퀴가 반시계 방향으로 회전하게 되고, 2번이 회전하기 때문에, 3번도 동시에 시계 방향으로 회전하게 된다. 4번은 3번이 회전하지만, 맞닿은 극이 같기 때문에 회전하지 않는다. 따라서, 아래와 같은 상태가 된다.

• 톱퀴는 총 1번부터 ~ 4번까지 번호로 매겨져 있다. 
• N극 0, S극 1
• 시계 방향 1, 반시계 뱡항은 -1

핵심 아이디어

• 구현 문제, 톱니바퀴의 왼쪽과 오른쪽을 탐색하면서 극이 일치하는지 일치하지 않는지를 판단해주면 된다. 
• 톱니바퀴를 돌리면서 탐색한다. 즉, 회전시킨다는 점에서 deque 자료구조 활용. deque에서는 rotate()를 지원하여 시계방향과 반시계 방향으로 회전이 가능하다. rotate() 함수 안에 음수를 넣으면 왼쪽 회전, 양수는 오른쪽 회전이다.
• 톱니바퀴 수가 n개 라면 DFS를 통해 재귀적으로 탐색할텐데 4개라 for loop 사용

코드 구현

# 입력 받는 부분
from collections import deque
# 톱니 상태 저장
t = [deque(list(map(int, input().split()))) for _ in range(4)]

# k번 반복한다.
k = int(input())
for _ in range(k):
	# (왼쪽[6번째], 오른쪽[2번째])
	init = [] # 톱니 바퀴의 (왼쪽[6번째], 오른쪽[2번째]) 담기
	for i in range(4):
		# 나중에 맞닿은 극이 같은지 확인하기 위함
		# 현재 톱니를 기준으로 (왼쪽[6번째], 오른쪽[2번째])
		init.append([t[i][6], t[i][2]])
	n, d = map(int, input().split())
	n = n - 1 # 1번이 아니라 0번부터 시작 0~ 3 번 톱니바퀴!

	# 톱니의 왼쪽 부분과 오른족 부분을 확인한다.
	# 1. 톱니의 왼쪽 확인 하기, 이때 0번째 톱니는 확인할 필요 없다.
	if n != 0:
		for i in range(n, 0, -1): # n번 부터 1번 톱니까지 확인
			if init[i][0] != init[i-1][1]: # 모든 톱니가 서로 극이 다르다면
				# 서로 반대 방향 으로 회전 한다.
                # 현재 톱니 바로 왼쪽(한칸 떨어진) 톱니는 서로 반대 방향
				# 현재 톱니와 2칸 떨어진 톱니는 서로 같은 방향
				if (n-(i-1)) % 2 == 0: # 거리가 짝수라면 2,4,6... 즉 
					# 왼쪽 톱니를 시계 방향으로 회전
					t[i-1].rotate(d)
				elif (n-(i-1)) % 2 != 0:
					# 왼쪽 톱니를 반시계 방향으로 회전
					t[i-1].rotate(-1*d)
			elif init[i][0] == init[i-1][1]: # 극이 같다면
				# 왼쪽 톱니는 회전하지 않는다.
				break

# 2. 톱니의 오른쪽 부분 확인, 가까 오른쪽인 3번 톱니는 확인 하지 않는다.
	if n != 3:
		for i in range(n, 3): # n부터 2까지 확인
			if init[i][1] != init[i+1][0]:
				if (n-(i+1)) % 2 == 0:
					# 오른쪽 톱니를 시계방향으로 회전
					t[i+1].rotate(d)
				elif (n-(i+1)) % 2 != 0:
					# 오른쪽 톱니를 반시계 방향으로 회전
					t[i+1].rotate(-1*d)
			elif init[i] == init[i+1]: # 오른쪽 톱니와 극이 같다면
				break # 회전하지 않는다.

from collections import deque

# 톱니 바퀴의 초기 상태를 담을 deque
t = [deque(list(map(int, input()))) for _ in range(4)]

# k번 반복한다.
k = int(input())
for _ in range(k):
	# (왼쪽[6번째], 오른쪽[2번째])
	init = [] # 톱니 바퀴의 (왼쪽[6번째], 오른쪽[2번째]) 담기
	for i in range(4):
		# 나중에 맞닿은 극이 같은지 확인하기 위함
		# 현재 톱니를 기준으로 (왼쪽[6번째], 오른쪽[2번째])
		init.append([t[i][6], t[i][2]])
	n, d = map(int, input().split())
	n = n - 1 # 1번이 아니라 0번부터 시작 0~ 3 번 톱니바퀴! 

	# 톱니의 왼쪽 부분과 오른족 부분을 확인한다.
	# 1. 톱니의 왼쪽 확인 하기, 이때 0번째 톱니는 확인할 필요 없다.
	if n != 0:
		for i in range(n, 0, -1): # n번 부터 1번 톱니까지 확인
			if init[i][0] != init[i-1][1]: # 극이 다르다면
				# 서로 반대 방향 으로 회전 한다.
				if (n-(i-1)) % 2 == 0:
					# 왼쪽 톱니를 시계 방향으로 회전
					t[i-1].rotate(d)
				elif (n-(i-1)) % 2 != 0:
					# 왼쪽 톱니를 반시계 방향으로 회전
					t[i-1].rotate(-1*d)
			elif init[i][0] == init[i-1][1]: # 극이 같다면
				# 왼쪽 톱니는 회전하지 않는다.
				break
	# 2. 톱니의 오른쪽 부분 확인, 가까 오른쪽인 3번 톱니는 확인 하지 않는다.
	if n != 3:
		for i in range(n, 3): # n부터 2까지 확인
			if init[i][1] != init[i+1][0]:
				if (n-(i+1)) % 2 == 0:
					# 오른쪽 톱니를 시계방향으로 회전
					t[i+1].rotate(d)
				elif (n-(i+1)) % 2 != 0:
					# 오른쪽 톱니를 반시계 방향으로 회전
					t[i+1].rotate(-1*d)
			elif init[i] == init[i+1]: # 오른쪽 톱니와 극이 같다면
				break # 회전하지 않는다.

# 이제 결과 출력하기
ans = 0
if t[0][0] == 1:
	ans += 1
if t[1][0] == 1:
	ans += 2
if t[2][0] == 1:
	ans += 4
if t[3][0] == 1:
	ans += 8
print(ans)

참고 블로그

https://pottatt0.tistory.com/entry/%EB%B0%B1%EC%A4%80-14891-%ED%95%B4%EC%84%A4-python-%ED%86%B1%EB%8B%88%EB%B0%94%ED%80%B4

[ 백준 14891 해설 ] ( python ) 톱니바퀴