[구현/백준] 15662번: 톱니바퀴(2)

- 문제 : https://www.acmicpc.net/problem/15662

 

문제 이해 

- 전체 T개의 톱니바퀴가 주어지고, 각각의 톱니바퀴의 각 바퀴 칸에는 N극 또는 S극이 있다. 

 

 

- 문제에서 특정 톱니바퀴가 돌면 옆에 있는 톱니바퀴는 움직이는 톱니바퀴와 맞닿아 있는 부분이 어떤지에 따라 움직일 수도 있고, 아닐 수도 있다. 

    - 맞닿아 있는 부분이 S극 - N극, N극 - S극 인 경우는 맞닿아 있는 톱니바퀴도 움직인다.

    - 이때 주의해야할 건 기존 톱니바퀴 방향과는 반대로 회전한다는 것이다. 기존 톱니바퀴가 시계방향(direction = 1)으로 돈다면, 맞닿아 있는 톱니바퀴는 반시계 방향(direction = -1)로 돈다. 반대 방향도 마찬가지이다. 

    - 기준 톱니바퀴의 오른쪽으로 맞닿은 톱니바퀴의 정확한 칸 위치는 10시 방향(인덱스 6 또는 -2) 바퀴이고, 왼쪽으로 맞닿은 톱니바퀴는 2시 방향(인덱스 2)이다. 

 

 

- 위에서 주어진 조건대로 맞닿아 있는 바퀴의 위치도 정해져 있고, 극이 다를 경우 서로 반대로 회전하는 것까지 알 수 있다. 하지만 내가 막혔던 부분은 하나의 바퀴가 돌 때 오른쪽 혹은 왼쪽으로 계속 회전할텐데 그거를 queue로 해야하나 싶었는데 어떻게 구현해야하는지 몰랐다. 

    - 풀이를 찾아보니 문제에서 회전하는 톱니바퀴가 주어졌을 때, 그 톱니바퀴를 기준으로 오른쪽과 왼쪽 각각 for문으로 진행하면서 돌아가는 조건을 만족하는 톱니바퀴를 모두 배열에 넣은 다음에 한번에 모두 둘리면 된다. 만약 극이 같은 게 나오면 그즉시 종료된다. 

        # t 기준 오른쪽 기어
        for i in range(t+1, T+1):
            if gears[i][-2] != gears[i-1][2]: 
            	turnElement.append(i)
            else: 
            	break
                
        # t 기준 왼쪽 기어
        for i in range(t-1, 0, -1):
            if gears[i][2] != gears[i+1][-2]: 
            	turnElement.append(i)
            else: 
            	break

 

   

    - 톱니바퀴가 돌아가는 것은 각각의 인덱스가 오른쪽, 왼쪽으로 한칸씩 이동하는 것이므로 deque의 rotate를 이용하면 쉽다. 

    - 그리고 그때 기준이 되는 톱니바퀴(t)의 바로 양옆에 있는 것은 반대로 돌지만, 그게 아닌 한칸 떨어진 것들은 모두 톱니바퀴 t와 같은 방향으로 돈다. (이부분 생각하기!)

        # t 기어 회전
        gears[t].rotate(direction)
        
        # t 기어와 맞닿은 극이 다른 기어 회전
        for element in turnElement:
            if (element - t) % 2 != 0 :
                gears[element].rotate(-direction)
            else:
                gears[element].rotate(direction)

 

 

- 회전하는 톱니바퀴 인덱스와 회전 방향이 주어지는데, 이를 turn 배열에 넣은 뒤 반복문을 돌리면서 위 과정을 진행하면 된다.

 

 

- 모든 톱니바퀴가 돌았다면 마지막에는 각 톱니바퀴에서 0 인덱스 값이 1인 톱니바퀴의 개수를 구해서 출력하면된다. (더 편하게 하기 위해선 개수를 안 세도 되고, 값이 1이므로 톱니바퀴의 0인덱스 값을 모두 더한 값을 출력해도 된다)

    return sum([gears[i][0] for i in range(1, T+1)])

 

정답 풀이 

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

def solution(T, gears, K, turn):
    for t, direction in turn:
        turnElement = []
        
        # t 기준 오른쪽 기어
        for i in range(t+1, T+1):
            if gears[i][-2] != gears[i-1][2]: 
            	turnElement.append(i)
            else: 
            	break
                
        # t 기준 왼쪽 기어
        for i in range(t-1, 0, -1):
            if gears[i][2] != gears[i+1][-2]: 
            	turnElement.append(i)
            else: 
            	break
                
        # t 기어 회전
        gears[t].rotate(direction)
        
        # t 기어와 맞닿은 극이 다른 기어 회전
        for element in turnElement:
            if (element - t) % 2 != 0 :
                gears[element].rotate(-direction)
            else:
                gears[element].rotate(direction)
            
    return sum([gears[i][0] for i in range(1, T+1)])

T = int(input())
gears = [0] + [deque(map(int,list(input().strip()))) for _ in range(T)]
K = int(input())
turn = [list(map(int, input().split())) for _ in range(K)]

res = solution(T, gears, K, turn)
print(res)

 

삽질한 코드,,,

wheels = []
t = int(input())
for _ in range(t):
    wheels.append(list(input()))

def move_straight(arr):
    temp = [arr[-1]]
    for i in range(len(arr) - 1):
        temp.append(arr[i])
    return temp 

def move_reverse(arr):
    temp = []
    for i in range(1, len(arr)):
        temp.append(arr[i])
    temp.append(arr[0])
    return temp
        
for _ in range(int(input())):
    number, direction = map(int, input().split())
    number -= 1
    
    if number == 0:
        if wheels[number][2] != wheels[number + 1][-2]:
            if direction == 1: # 시계방향이면 옆에는 반시계로
                wheels[number + 1] = move_reverse(wheels[number + 1])
            elif direction == -1:
                wheels[number + 1] = move_straight(wheels[number + 1])
    elif number == t - 1:
        if wheels[number][-2] != wheels[number - 1][2]:
            if direction == 1: # 시계방향이면 옆에는 반시계로
                wheels[number - 1] = move_reverse(wheels[number - 1])
            elif direction == -1:
                wheels[number - 1] = move_straight(wheels[number - 1])
    else:
        if wheels[number][2] != wheels[number + 1][-2]:
            if direction == 1:
                wheels[number + 1] = move_reverse(wheels[number + 1])
            elif direction == -1:
                wheels[number + 1] = move_straight(wheels[number + 1])
        if wheels[number][-2] != wheels[number - 1][2]:
            if direction == 1:
                wheels[number - 1] = move_reverse(wheels[number - 1])
            elif direction == -1:
                wheels[number - 1] = move_straight(wheels[number - 1])

answer = 0  
for wheel in wheels:
    if wheel[0] == '1':
        answer += 1
        
print(answer)

 

 

참고 블로그 

https://velog.io/@isayaksh/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-BOJ-15662-%ED%86%B1%EB%8B%88%EB%B0%94%ED%80%B4-2-Python