[백준 14891번-톱니바퀴]-파이썬

solved.ac 난이도 : GOLD5

백준   14891번- 파이썬 풀이

 

<문제>

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

14891번: 톱니바퀴

<풀이>-구현,시뮬레이션

이 문제를 접근할때 우선 크게 두가지 부분으로 나눠서 접근을 했다. 하나는 회전시키는 부분을 구현하는 함수이고 두번째는 회전이 가능한 톱니바퀴의 리스트를 만드는 것이었다. 회전이 가능한 톱니바퀴의 리스트를 만들때 큐를 이용해 구현해봤다.

 

-회전시키는 부분-

우선 함수의 매개변수로 배열과 회전방향을 담는 변수를 설정했다.

회전시킨 이후의 상황을 저장할 temp배열을 선언한 후 다음과 같이 회전을 진행했다.

def rotate(a,array):
    temp = [0]*8
    if a == -1: #반시계방향
        temp[7] = array[0]
        for i in range(1,len(array)):
            temp[i-1] = array[i]
    if a == 1: #시계방향
        temp[0] = array[7]
        for i in range(len(array)-1):
            temp[i+1] = array[i]
    return temp

이 부분을 구현하는데에는 큰 어려움은 없었다. 이 코드를 천천히 살펴보면 어떤 방식으로 했는지 이해가 될것이다.

 

-회전시킬 톱니바퀴의 리스트를 만드는 부분-

이 부분을 구현할때 생각보다 많은 고민을 했다. 한 톱니바퀴를 회전시켰을때 두칸 떨어진 톱니바퀴까지 연속적으로 회전이 가능하다는 점에서 큐를 사용했다. 이 부분은  bfs문제를 풀때와 많이 비슷했다.

서로 인접한 톱니바퀴가 양쪽으로 있기 때문에 각각 구현해야했다.

 

오른쪽의 톱니바퀴와 인접한 경우는 톱니바퀴의 세번째 부분과 오른쪽 톱니바퀴의 7번째 부분(아홉시 방향)이 맞닿는다.

 

반대로 왼쪽 톱니바퀴와 인접한 부분은 톱니바퀴의 7번째 부분과(아홉시방향) 왼쪽 톱니바퀴의 세번째 부분이 맞닿는다.

 

필자는 왼쪽 오른쪽 모두 세번째 부분이 맞닿는걸로 착각해 이 부분에서 어렴을 겪었다.

 

이 함수에서 회전이 가능한 톱니바퀴의 리스트를 반환한 후 이 리스트의 원소들을 회전시키는 함수에 매개변수로 넣어 최종 결과를 완성했다.

 

def check(a,dir):
    rotate_list = []
    visitied = [False]*4
    queue = deque()
    queue.append((a-1,dir))
    visitied[a-1] = True
    rotate_list.append((a-1,dir))
    while queue:
        x,dir = queue.popleft()
        #왼쪽톱니바퀴와 맞닿을때
        nx = x-1
        if (0<=nx<4 and topni[nx][2] != topni[x][6] and not visitied[nx]):
            queue.append((nx,-dir))
            rotate_list.append((nx,-dir))
            visitied[nx] = True
        #오른쪽 톱니바퀴와 맞닿을때
        nx = x+1
        if(0<=nx<4 and topni[nx][6] != topni[x][2] and not visitied[nx]):
            queue.append((nx,-dir))
            rotate_list.append((nx,-dir))
            visitied[nx] = True
    return rotate_list

위 코드에서 dir은 방향을 의미한다.

그리고 큐에 삽입할때 -dir을 해주는 이유는 인접한 톱니바퀴는 반대로 회전하기 때문이다.

 

따라서 최종코드는 다음과 같다.

반응형

728x90

<코드>-파이썬

 

from collections import deque
def rotate(a,array):
    temp = [0]*8
    if a == -1: #반시계방향
        temp[7] = array[0]
        for i in range(1,len(array)):
            temp[i-1] = array[i]
    if a == 1: #시계방향
        temp[0] = array[7]
        for i in range(len(array)-1):
            temp[i+1] = array[i]
    return temp


score = [1,2,4,8]
topni = []


for _ in range(4):
    topni.append(list(map(int,input()))) 
k = int(input())

def check(a,dir):
    rotate_list = []
    visitied = [False]*4
    queue = deque()
    queue.append((a-1,dir))
    visitied[a-1] = True
    rotate_list.append((a-1,dir))
    while queue:
        x,dir = queue.popleft()
        #왼쪽톱니바퀴와 맞닿을때
        nx = x-1
        if (0<=nx<4 and topni[nx][2] != topni[x][6] and not visitied[nx]):
            queue.append((nx,-dir))
            rotate_list.append((nx,-dir))
            visitied[nx] = True
        #오른쪽 톱니바퀴와 맞닿을때
        nx = x+1
        if(0<=nx<4 and topni[nx][6] != topni[x][2] and not visitied[nx]):
            queue.append((nx,-dir))
            rotate_list.append((nx,-dir))
            visitied[nx] = True
    return rotate_list

for _ in range(k):
    number,direc = map(int,input().split())
    rotate_list= check(number,direc)
    for i,j in rotate_list:
        topni[i] = rotate(j,topni[i])


sum = 0    
for i in range(len(topni)):
    if topni[i][0] == 0:
        sum+=0
    if topni[i][0] == 1:
        sum+=score[i]
print(sum)

톱니바퀴의 번호별로 점수가 다르기 때문에 score리스트를 만들어 톱니바퀴의 번호와 score 리스트의 인덱스를 갖게 해 점수를 더해 주었다.

 

-마치며-

 

최근에 이런저런 개인사정이 많아 문제를 오랜만에 풀게 되었는데 역시 오랜만이라 그런지 감이 많이 죽은거 같았다. 또한 이 문제에서 아주사소한 실수로 인해 시간을 많이 잡아 먹었는데 그부분이 좀 아쉬웠다.