[삼성SW기출문제] 14891번 톱니바퀴

1. 문제 링크

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

14891번: 톱니바퀴

 

2. 코드

- 문제 소요 시간: 1시간 30분

import math
from collections import deque

state = [deque(list(map(int, input()))) for _ in range(4)]
n = int(input())
rotate = [list(map(int, input().split())) for _ in range(n)]

q = deque()
def bfs(Num, Dir, Q):
    q.append((Num, Dir))

    while q:
        num, dir = q.popleft()
        if num < 3 and not visit[num + 1]:
            visit[num + 1] = True
            if state[num][2] != state[num + 1][6]:  # 오른쪽 톱니바퀴 체크
                q.append((num + 1, -dir))
                Q.append((num + 1, -dir))

        if num > 0 and not visit[num - 1]:
            visit[num - 1] = True
            if state[num][6] != state[num - 1][2]:  # 왼쪽 톱니바퀴 체크
                q.append((num - 1, -dir))
                Q.append((num - 1, -dir))

for num, dir in rotate:
    visit = [False for _ in range(4)]
    Q = deque()
    Q.append((num - 1, dir))
    visit[num - 1] = True
    bfs(num - 1, dir, Q)

    while Q:
        num, dir = Q.popleft()
        state[num].rotate(dir)  # 톱니바퀴 회전

answer = 0
for i in range(4):
    if state[i][0] == 0:
        continue
    answer += math.pow(state[i][0] * 2, i)

print(int(answer))

 

3. 문제 풀이

- 적용 알고리즘: 구현 + BFS

- 포인트

1. 회전을 어떻게 할 것인가?
   1. 처음에 문제를 읽고, 양방향으로 회전한다고 해서 바로 deque를 사용하고 rotate() 메서드를 사용해야 겠다고 생각함.
   2. 마침, 주어진 방향도 rotate에 적용되는 것과 같아서 더 편했음.
      1. 참고) rotate(-1) : 반시계 방향
2. 회전을 언제 할 것인가?
   1. 이 것 때문에 시간을 많이 잡아먹었다. 처음에는 dfs로 구현하면서 톱니바퀴 한 개씩 회전을 시켜줬다. 그러다 보니 톱니바퀴 회전은 한 번에 일어나야 되는데 한 개씩 일어나다 보니 상태 변화가 생겨 꼬이는 현상이 발생했다.
   2. 그래서 두 번째 생각한 방법은 bfs로 구현하고, 회전 시켜야할 톱니바퀴와 방향을 저장해두고 한 번에 회전시키고자 했다.