난이도

Gold 5

풀이 참고 유무

X

막힌 부분

X

문제

문제 바로가기

입력

첫째 줄에 톱니바퀴의 개수 T (1 ≤ T ≤ 1,000)가 주어진다.
둘째 줄부터 T개의 줄에 톱니바퀴의 상태가 가장 왼쪽 톱니바퀴부터 순서대로 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.
다음 줄에는 회전 횟수 K(1 ≤ K ≤ 1,000)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

출력

총 K번 회전시킨 이후에 12시방향이 S극인 톱니바퀴의 개수를 출력한다.

예제 입력

5
10010011
01010011
11100011
01010101
01010011
10
1 1
2 1
3 1
4 1
1 -1
2 -1
3 -1
4 -1
5 1
5 -1

예제 출력

5

문제 검토

톱니바퀴가 하나가 움직이면 다른 톱니바퀴에도 영향을 준다.
계속 같은 작업을 한 칸씩 이동하면서 하기 때문에 재귀를 생각할 수 있다.

또한 회전한다는 점에서 이전에 컨베이어 벨트 위의 로봇
문제에서 사용했던 deque의 rotate 함수를 떠올릴 수 있다.

풀이(python)

Python

from collections import deque
t=int(input())
con=[deque(map(int,input())) for _ in range(t)]
k=int(input())
case=[list(map(int,input().split())) for _ in range(k)]
right=2
left=6
#왼쪽방향 회전
def Leftrot(c,l,cs):      
    #왼쪽 끝이면 리턴   
    if c==0:    
        return    
    #회전하기 전 9시방향 극을 담아놓음
    nl=con[c-1][left]    
    #회전하기 전 3시방향 극을 담아놓음
    r=con[c-1][right]
    #이전 톱니바퀴의 9시방향과 현재 톱니바퀴의 3시방향의 극이 같다면 리턴
    if l==r:        
        return
    #아니라면 회전 후 다음 톱니바퀴로 들어감
    else:
        if cs>0:
            con[c-1].rotate(-1)
            Leftrot(c-1,nl,-1)
        else:
            con[c-1].rotate(1)
            Leftrot(c-1,nl,1)
#오른쪽방향 회전            
def Rightrot(c,r,cs):         
    if c==t-1:        
        return
    nr=con[c+1][right]    
    l=con[c+1][left]
    if r==l:        
        return
    else:
        if cs>0:
            con[c+1].rotate(-1)
            Rightrot(c+1,nr,-1)
        else:
            con[c+1].rotate(1)
            Rightrot(c+1,nr,1)            
for cas in case:
    nr=con[cas[0]-1][right]
    nl=con[cas[0]-1][left]      
    #해당 톱니바퀴 회전
    con[cas[0]-1].rotate(cas[1])
    Leftrot(cas[0]-1,nl,cas[1])
    Rightrot(cas[0]-1,nr,cas[1])    
#결과    
result=0
for x in con:
    if x[0] == 1:
        result+=1
print(result)
     

1. case의 해당 톱니바퀴를 먼저 회전시킴
2. 양방향으로 회전해나감

걸린 시간

31:22

총평

이전에 컨베이어 벨트 위의 로봇 문제에서 사용했던 rotate 함수의 존재를 떠올리지 못했다면 매우 복잡해졌을 것이다.

또한 이전에 DFS와 여러 재귀문제들을 풀면서 재귀를 사용하는 것에 익숙해지지 않았다면 매우 힘들게 문제를 풀었을 것이다.
BFS처럼 큐를 사용해서 푸는 방법도 있겠지만 재귀를 이용해 먼저 한쪽 방향의 톱니바퀴들을 모두 회전 시키고 다른 방향의 톱니바퀴들을 회전 시키는 방법이 적절하다고 생각 했다.

알고리즘은 기출문제처럼 많은 양의 문제를 풀면 풀수록 도움이 된다는 것을 알게 해준 문제이다.