[BOJ] 15662. 톱니바퀴 (2)

Python3

문제

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

키워드

• 구현
• 시뮬레이션

문제 풀이

문제 요구사항

총 8개의 톱니를 가지고 있는 톱니바퀴 T개가 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다.
톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, ..., 가장 오른쪽 톱니바퀴는 T번이다.

톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸 기준. 회전은 시계 방향과 반시계 방향.

톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다.

톱니바퀴 T개의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램

변수 및 함수 설명

• t: 톱니바퀴의 개수 (1 ≤ T ≤ 1,000)
• k: 회전 횟수 (1 ≤ K ≤ 1,000)
• wheel: 톱니바퀴의 상태. 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1
• cnt: 총 K번 회전시킨 이후에 12시방향이 S극인 톱니바퀴의 개수
• num, dir: num은 회전시킨 톱니바퀴의 번호, dir는 방향. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향

• left(start, dirs): 왼쪽 톱니 조사 함수
• right(start, dirs): 오른쪽 톱니 조사 함수

풀이

(입력 및 선언)

• 톱니바퀴의 개수를 입력받는다
• 톱니바퀴의 개수만큼 상태를 입력받고 deque을 사용해 wheel 리스트에 저장한다.
  (rotate 함수를 사용하기 위한 덱 사용)
• 회전 횟수인 k를 입력받고 총 k번 반복한다.
• 회전시킬 톱니바퀴 번호와 방향을 입력받는다.
• 이때 톱니바퀴 번호는 1부터 시작하지만, 리스트는 0부터 시작하므로 -1을 해준다.
• left 함수로 왼쪽 톱니를 조사하고, right 함수로 오른쪽 톱니를 조사할 것이다.
• 인자는 왼쪽 조사일 때는 현재 톱니바퀴의 왼쪽 톱니(num-1)과 -dir이다.
• 오른쪽 조사일 때는 현재 톱니바퀴의 오른쪽 톱니(num+1)과 -dir이다.
• -dir인 이유는 회전할 톱니번호가 회전하는 방향의 반대방향으로 회전해야 하기 때문
• 현재 톱니바퀴도 dir 방향대로 rotate 시킨다.

(왼쪽 톱니바퀴 조사)

• 만약 톱니가 0보다 작다면 (즉, 첫 번째 톱니를 돌리는 것이라면) 확인할 필요 없다.
• 만약 톱니의 2번째 원소와 현재 톱니의 6번째 원소가 다르다면, 그 왼쪽 톱니바퀴도 조사한다.
• 그리고 현재 톱니를 방향대로 돌린다

(오른쪽 톱니바퀴 조사)

• 만약 톱니가 t-1보다 크다면 (즉, 마지막 톱니를 돌리는 것이라면) 확인할 필요 없다.
• 만약 톱니의 6번째 원소와 이전 톱니의 2번째 원소가 다르면, 그 오른쪽 톱니바퀴도 조사한다.
• 현재 톱니를 방향대로 돌린다.

(최종 출력)

• 총 K번 회전시킨 이후에 12시방향이 S극인(배열의 첫 번째 원소가 1인) 톱니바퀴의 개수를 출력한다.

최종 코드

from collections import deque

wheel = []
cnt = 0

def left(start, dirs):
    if start < 0:
        return
    if wheel[start][2] != wheel[start+1][6]:
        left(start-1, -dirs)
        wheel[start].rotate(dirs)

def right(start, dirs):
    if start > t - 1:
        return
    if wheel[start][6] != wheel[start-1][2]:
        right(start+1, -dirs)
        wheel[start].rotate(dirs)

t = int(input())

for _ in range(t):
    wheel.append(deque(input()))

k = int(input())

for _ in range(k):
    num, dir = map(int, input().split())
    num -= 1

    left(num-1, -dir)
    right(num+1, -dir)
    wheel[num].rotate(dir)

for i in range(t):
    if wheel[i][0] == '1':
        cnt += 1

print(cnt)

피드백

톱니바퀴 1 문제와 다르게 톱니바퀴 개수를 입력받는 문제였다.
따라서 right() 함수를 구현할 때 인덱스 범위를 잘 설정해주어야 IndexError가 나지 않는다.