문제 이해
총 4개의 톱니바퀴가 있다. 왼쪽부터 차례대로 1, 2, 3, 4번이고 각각의 톱니바퀴의 톱니에는 N,S가 써져있다. 1번째 톱니바퀴를 시계방향으로 돌린다고 가정할 때 2번째 톱니바퀴와 맞닿는 부분이 N, S중 같다면 2번째 톱니바퀴는 돌아가지 않는다. 만약 다르다면 2번째 톱니바퀴는 반시계방향으로 돌아간다. 그럼 또 같은 방식으로 연쇄반응이 일어난다.
문제에서 주어진 명령을 모두 수행했을 때 12시방향에 있는 S의 개수를 알아야한다.
입력
첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.
다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.
출력
총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.
- 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
- 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
- 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
- 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점
문제 접근
이 문제를 보고 나는 4가지 단계로 나누었다.
- 톱니바퀴를 돌리는 것
- 오른쪽 톱니바퀴와 왼쪽 톱니바퀴가 돌아가는지 확인할 것
- 만약 돌아간다면 돌릴 것
- 명령을 모두 수행한 후 점수를 계산할 것
문제 해결
톱니바퀴를 돌리는 것
deque의 rotate함수를 사용하여 구현했다. 파라미터로 회전시킬 톱니바퀴 번호와 방향을 받는다.
def turn(number, direction): # number는 회전시킬 톱니바퀴 번호
if direction==1: #시계방향 오른쪽으로 한칸
gears[number].rotate(1)
else : # 반시계방향 왼쪽으로 1칸
gears[number].rotate(-1)오른쪽 톱니바퀴와 왼쪽 톱니바퀴가 돌아가는지 확인할 것
number가 범위 밖으로 나갈 경우 False 맞닿은 부위가 다를 경우 True를 반환하여 돌아간다는 것을 return한다.
파라미터로는 돌려야하는 톱니바퀴의 번호와 돌리려고 하는 톱니바퀴의 맞닿은 부분의 값을 넣어줬다.
# i = 2인게 오른쪽
# i = 6인게 왼쪽
def can_turn_left(number,l): #왼쪽 톱니바퀴가 돌아가는가?
if number<0:
return False
if gears[number][2]!=l:
return True
return False
def can_turn_right(number,r): #오른쪽 톱니바퀴가 돌아가는가?
if number>3:
return False
if r!=gears[number][6]:
return True
return False만약 돌아간다면 돌릴 것 - BFS
- 범위 밖이라면 종료
- 현재의 맞닿은 부분을 r,l에 저장
- 돌리고 현재 톱니바퀴 돌렸다고 표시
- 왼쪽, 오른쪽 톱니바퀴를 돌릴 수 있는지 확인하고 돌릴 수 있다면 재귀
- 현재함수 종료
def what_direction_turn(number,direction):
if number>3 or number<0:
return
r, l = gears[number][2], gears[number][6]
turn(number,direction)
visited[number]=True
if can_turn_right(number+1,r) and visited[number+1]==False:
what_direction_turn(number+1,-direction)
if can_turn_left(number-1,l) and visited[number-1]==False:
what_direction_turn(number-1,-direction)
return명령을 모두 수행하고 점수 계산하기
각각의 명령을 for문으로 모두 실행해준다.
점수를 계산한다.
for number, direction in do:
visited = [False for _ in range(4)]
what_direction_turn(number-1,direction)
answer = 0
if gears[0][0]==1:
answer+=1
if gears[1][0]==1:
answer+=2
if gears[2][0]==1:
answer+=4
if gears[3][0]==1:
answer+=8제출 코드
간단한 구현문제인듯하다
import sys
from collections import deque
import copy
gears = []
for _ in range(4):
gears_str = str(sys.stdin.readline().rstrip())
gears.append(deque([int(i) for i in gears_str]))
K = int(sys.stdin.readline())
do = []
for i in range(K):
do.append(list(map(int,sys.stdin.readline().split())))
# i = 2인게 오른쪽
# i = 6인게 왼쪽
def can_turn_left(number,l): #왼쪽 톱니바퀴가 돌아가는가?
if number<0:
return False
if gears[number][2]!=l:
return True
return False
def can_turn_right(number,r): #오른쪽 톱니바퀴가 돌아가는가?
if number>3:
return False
if r!=gears[number][6]:
return True
return False
def what_direction_turn(number,direction):
if number>3 or number<0:
return
r, l = gears[number][2], gears[number][6]
turn(number,direction)
visited[number]=True
if can_turn_right(number+1,r) and visited[number+1]==False:
what_direction_turn(number+1,-direction)
if can_turn_left(number-1,l) and visited[number-1]==False:
what_direction_turn(number-1,-direction)
return
def turn(number, direction): # number는 회전시킬 톱니바퀴
if direction==1: #시계방향 오른쪽으로 한칸
gears[number].rotate(1)
else : # 반시계방향 왼쪽으로 1칸
gears[number].rotate(-1)
for number, direction in do:
visited = [False for _ in range(4)]
what_direction_turn(number-1,direction)
answer = 0
if gears[0][0]==1:
answer+=1
if gears[1][0]==1:
answer+=2
if gears[2][0]==1:
answer+=4
if gears[3][0]==1:
answer+=8
print(answer)