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

문제보러가기

해당 문제는 4개의 톱니바퀴가 동일하게 존재하고, 입력으로 몇번째 톱니바퀴가 어느방향(시계 :1, 반시계:-1)으로 움직일지 주어지면 해당 입력에 맞게 톱니바퀴가 움직이고, 다른 톱니바퀴들은 아래 그림과 같이 맞닿는 면의 극이 같으면 회전하지 않고, 다르다면 맞닿는 톱니바퀴의 반대방향으로 회전한다.

문제 유형

• 시간 제한 : 2초
• 메모리 제한 : 512MB
• 입력 제한 : 회전 횟수(1<=K<=100)
• 알고리즘 : 구현
• 톱니바퀴를 구현으로 돌리면서 탐색한다
• 회전하는 함수를 하나 구현하고, 해당 톱니바퀴가 회전하면서 주변 톱니바퀴도 회전할지 여부를 체크하는 함수도 따로 구현한다.

해당 문제는 회전 횟수(1<=K<=100) 100이하이므로, 단순 구현으로 문제를 풀수있다.

풀이

• 회전하는 코드

def solution(x,y,t):
    tmp=a[x-1]
    b=copy.deepcopy(tmp)
    if y==1:
        for i in range(len(tmp)):
            tmp[i]=b[i-1]
    elif y==-1:
        for i in range(len(tmp)-1, -1, -1):
            tmp[i-1]=b[i]
    check(x,y,t,b)

이 코드는 먼저 회전방향(y)에 따라 회전하는 방법을 다르게 정의해줬고, 회전이 끝나면 check()함수를 통해 주변 톱니바퀴도 회전해야하는지 찾아줬다

def check(x, y, t, b):
    if x+1<=4:
        if b[2]!=a[x][6] and visit[t][x+1]:
            visit[t][x+1]=0
            solution(x+1, -y,t)
    if x-1>=1:
        if b[6]!=a[x-2][2] and visit[t][x-1]:
            visit[t][x-1]=0
            solution(x-1, -y,t)

이 함수에서는 맞닿는 면의 극이 같은지, 다른지 확인하고 다르면 반대방향으로 회전할수있도록 다시 solution함수를 호출해줬다.

여기서 주의할 점은, visit배열의 사용인데 visit[t][x+1]에서 t는 테스트 케이스 순서이다.

• 전체 코드

import sys
input=sys.stdin.readline
import copy
from collections import deque


def solution(x,y,t):
    tmp=a[x-1]
    b=copy.deepcopy(tmp)
    if y==1:
        for i in range(len(tmp)):
            tmp[i]=b[i-1]
    elif y==-1:
        for i in range(len(tmp)-1, -1, -1):
            tmp[i-1]=b[i]
    check(x,y,t,b)
def check(x, y, t, b):
    if x+1<=4:
        if b[2]!=a[x][6] and visit[t][x+1]:
            visit[t][x+1]=0
            solution(x+1, -y,t)
    if x-1>=1:
        if b[6]!=a[x-2][2] and visit[t][x-1]:
            visit[t][x-1]=0
            solution(x-1, -y,t)
                    
                
        
a=[]       
for i in range(4):
    tmp=list(map(int, input().rstrip()))
    a.append((tmp))

k=int(input())
visit=[[1]*5 for _ in range(k+1)]
t=0
for i in range(k):
    x,y=map(int, input().split())
    visit[t][x]=0
    solution(x,y,t)
    t+=1
result=[]
multi=1
for i in range(1,5):
 
    if a[i-1][0]==1:
        temp=multi
    else:
        temp=0
    result.append(temp)        
    multi*=2
print(sum(result))

문제를 맞추고 , 다른 분들의 코드들도 참고하였는데 내 코드보다 훨씬 간단했다.
요점은 deque()를 사용하여 회전하는 코드를 deque().rotate()를 통해 구현하였다.

다른 분의 코드 참고

# ✨ 입력
import sys
from collections import deque
input = sys.stdin.readline
t = [deque(list(map(int,input().rstrip()))) for _ in range(4)] # 톱니 상태 저장

# ✨ 톱니 돌리기 
k = int(input())
for _ in range(k): 
	r = [] # ✨ 처음 톱니 상태 저장
	for i in range(4):
		r.append([t[i][6],t[i][2]])
	n,d = map(int,input().split())
	n = n-1
    
    # ✨ 왼쪽에 있는 톱니들 돌리기
	if n != 0 :
		for i in range(n,0,-1):
			if r[i][0] != r[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 r[i][0] == r[i-1][1]:
				break
                
	# ✨ 오른쪽에 있는 톱니들 돌리기
	if n != 3:
		for i in range(n,3):
			if r[i][1] != r[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 r[i][1] == r[i+1][0]:
				break
	t[n].rotate(d)
    
# ✨ 출력
res = 0
if t[0][0] == 1:
	res+=1
if t[1][0] == 1:
	res+=2
if t[2][0] == 1:
	res+=4
if t[3][0] ==1:
	res+=8
print(res)

• rotate 함수안에 음수를 넣게 된다면 왼쪽회전 양수는 오른쪽회전이다.

참고 코드