14891. [Python]톱니바퀴

1. 문제

 

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

 

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 512MB
• 구현
• 시뮬레이션

 

3. 파이썬 코드

 

import sys
from collections import deque
# 시계 방향 회전
def right(target):
    check = matrix[target].pop()
    matrix[target].appendleft(check)
# 반시계 방향 회전
def left(target):
    check = matrix[target].popleft()
    matrix[target].append(check)
# 연결된 톱니바퀴 체크
def DFS(start,dir):
    # 방문처리를 통해 연결된 톱니바퀴 회전
    visited = [0,0,0,0]
    visited[start-1] = 1
    # 첫 톱니바퀴 회전
    if dir == -1:
        left(start-1)
    else:
        right(start-1)
    queue = deque([start-1])
    # 연결된 톱니바퀴 중 극이 다른 톱니바퀴 회전 시킴
    while queue:
        next = queue.popleft()
        if next != start-1:
            if next%2 != (start-1)%2:
                if dir == -1:
                    right(next)
                else:
                    left(next)
            else:
                if dir == -1:
                    left(next)
                else:
                    right(next)
        for k in range(4):
            if flag[next][k] == 1 and visited[k] == 0:
                visited[k] = 1
                queue.append(k)

input = sys.stdin.readline

matrix = [deque(list(map(int,input().strip()))) for _ in range(4)]

K = int(input())

for _ in range(K):
    number, direction = map(int,input().split())
    flag = [[0,0,0,0] for _ in range(4)]
    # 처음 톱니바퀴들의 상태를 돌며 극이 다른 톱니바퀴들을 flag 라는 2차원 배열로 체크
    for i in range(4):
        if i == 0:
            if matrix[i][2] != matrix[i+1][6]:
                flag[i][i+1] = 1
        elif i == 3:
            if matrix[i][6] != matrix[i-1][2]:
                flag[i][i-1] = 1
        else:
            if matrix[i][2] != matrix[i+1][6]:
                flag[i][i+1] = 1
            
            if matrix[i][6] != matrix[i-1][2]:
                flag[i][i-1] = 1
    
    DFS(number,direction)
# 정답을 계산할 반복문
answer = 0
for k in range(4):
    # S극의 경우 2**n 으로 점수를 계산
    if matrix[k][0] == 1:
        answer += 2**k
print(answer)

 

4. 문제를 풀고난 후 생각

 

• 시뮬레이션 문제의 경우 직접 그려가면서 어떻게 동작하는지를 파악하면 코드로 구현하는 문제이다.
• 처음 했던 생각은 톱니바퀴가 어떻게 돌아야 하는지를 먼저 생각했고, 연결된 부분에 대해서 어떤 식으로 표현할지를 고민했다.

 

• 위와 같은 경우 3번이 처음 반시계로 돌게되면 양 옆의 톱니바퀴는 시계로 돌고 1번의 경우는 반시계로 도는 동작을 하게되는 것을 알았다.
• 이렇게 각 연결된 톱니바퀴들이 극이 다른 경우 flag의 2차원 배열을 통해서 1로 극이 다른 것을 인지시켰고, DFS를 돌면서 시작점과 연결된 톱니 바퀴 중 극이 다른 경우 deque() 리스트에 추가시켰고, 인덱스 번호에 따라서 %2 나머지 연산을 통해서 양 옆에 붙은 것인지 멀리 떨어진 부분인지에 따라서 돌리는 방향을 다르게 설정했다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 구현
• 시뮬레이션