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

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

14891번: 톱니바퀴

톱니바퀴가 돌아가는 걸 구하는 문제입니다.

이 문제는 간단하게

rotate 함수를 활용해도 되지만

공부의 관점에서 다른 방식을 사용했습니다.

 

저는 list로 풀이라는 법

deque로 풀이하는 법

2가지를 보여드릴 건데요

우선 큰 틀에서 먼저 접근해보겠습니다.

우선, 바퀴를 돌리고

양 옆의 바퀴를 보는 것입니다.

돌릴 바퀴를 기준으로

돌릴바퀴[2] 오른쪽[6]

돌릴바퀴[6] 왼쪽[2]

각각을 비교해줍니다.

그리고 돌리는 것이 가능하다면

rotate라는 deque에 넣어줍니다.

BFS하듯이

집어넣어주면 됩니다.

그 후, 탐색이 완료되면

각각의 바퀴를 돌려줍니다.

 

#백준 14891 톱니바퀴
from collections import deque

graph=[list(map(int,input())) for _ in range(4)]

K=int(input())
for _ in range(K):
  num,ro=map(int,input().split())
  num-=1
  visited=[False]*4
  visited[num]=True
  #현재 num에서 돌릴 수 있는 거 확인
  q=deque()
  q.append([num,ro])
  rotate=deque()
  rotate.append([num,ro])
  while q:
    n_num,n_ro=q.popleft()
    n_ro_b=n_ro*(-1)
    #왼쪽 오른쪽 각각 비교

    #왼쪽 비교
    if n_num-1>=0:
      if graph[n_num][6]!=graph[n_num-1][2] and not visited[n_num-1]:
        visited[n_num-1]=True
        q.append([n_num-1,n_ro_b])
        rotate.append([n_num-1,n_ro_b])

    #오른쪽 비교
    if n_num+1<4:
      if graph[n_num][2]!=graph[n_num+1][6] and not visited[n_num+1]:
        visited[n_num+1]=True
        q.append([n_num+1,n_ro_b])
        rotate.append([n_num+1,n_ro_b])
  #rotate deque에 있는 거 그대로 돌려주기
  while rotate:
    n_num,n_ro=rotate.popleft()
    if n_ro==1:
      graph[n_num][0],graph[n_num][1],graph[n_num][2],graph[n_num][3],graph[n_num][4],graph[n_num][5],graph[n_num][6],graph[n_num][7]=graph[n_num][7],graph[n_num][0],graph[n_num][1],graph[n_num][2],graph[n_num][3],graph[n_num][4],graph[n_num][5],graph[n_num][6]
    else:
      graph[n_num][0],graph[n_num][1],graph[n_num][2],graph[n_num][3],graph[n_num][4],graph[n_num][5],graph[n_num][6],graph[n_num][7]=graph[n_num][1],graph[n_num][2],graph[n_num][3],graph[n_num][4],graph[n_num][5],graph[n_num][6],graph[n_num][7],graph[n_num][0]
answer=0
for i in range(4):
  if graph[i][0]==1:
    answer+=2**i

print(answer)

 

 

바퀴를 리스트로 받을 때

구하는 방식입니다.

시계,반시계에 따라서 구하긴 했는데

돌리는 코드가

한줄에 너무 길어서

헷갈리실 수도 있습니다.

 

deque로 구할 때

머릿속으로 그려본 상황입니다.

코드로 직접 보겠습니다.

 

#백준 14891 톱니바퀴
from collections import deque

graph=[deque(map(int,input())) for _ in range(4)]
K=int(input())
for _ in range(K):
  num,ro=map(int,input().split())
  num-=1
  visited=[False]*4
  visited[num]=True
  #현재 num에서 돌릴 수 있는 거 확인
  q=deque()
  q.append([num,ro])
  rotate=deque()
  rotate.append([num,ro])
  while q:
    n_num,n_ro=q.popleft()
    n_ro_b=n_ro*(-1)
    #왼쪽 오른쪽 각각 비교

    #왼쪽 비교
    if n_num-1>=0:
      if graph[n_num][6]!=graph[n_num-1][2] and not visited[n_num-1]:
        visited[n_num-1]=True
        q.append([n_num-1,n_ro_b])
        rotate.append([n_num-1,n_ro_b])

    #오른쪽 비교
    if n_num+1<4:
      if graph[n_num][2]!=graph[n_num+1][6] and not visited[n_num+1]:
        visited[n_num+1]=True
        q.append([n_num+1,n_ro_b])
        rotate.append([n_num+1,n_ro_b])
  #rotate deque에 있는 거 그대로 돌려주기
  while rotate:
    n_num,n_ro=rotate.popleft()
    if n_ro==1:
      graph[n_num].appendleft(graph[n_num].pop())
    else:
      graph[n_num].append(graph[n_num][0])
      graph[n_num].popleft()

answer=0
for i in range(4):
  if graph[i][0]==1:
    answer+=2**i

print(answer)

코드 가독성 측면에서는

deque에서 append와 pop를 활용한 것이

좀 더 좋아보입니다.

시간차이는 비슷하긴한데

좀 더 스마트하게 풀 수 있는 느낌입니다.