- 문제 : 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)
참고 블로그
'백준 > 구현' 카테고리의 다른 글
| [구현/백준] 2636번 : 치즈 (0) | 2023.10.04 |
|---|---|
| [구현/백준] 15686번 : 치킨 배달 (2) | 2023.10.02 |
| [구현/백준] 7490번 : 0 만들기 (0) | 2023.09.14 |
| [구현/백준] 14719번 : 빗물 (0) | 2023.09.13 |
| [구현/백준] 20055번 : 컨베이어 벨트 (0) | 2023.09.12 |
