[백준] 14891번 톱니바퀴 (python)

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

---

 

접근 방식

문제를 보자마자 연쇄적으로 톱니바퀴가 돌아가니 DFS로 풀어야겠다고 생각했다.

근데 이제 돌아가는 방향을 고려해야 했고, 자석의 극성도 확인해야 됐다.. 톱니바퀴가 무조건 연쇄적으로 돌아가는 게 아니기 때문에 고려해야 할 부분이 많았다. 그래서 회전 부분은 left, right 각각 메서드로 분리했다.

 

DFS 부분 풀이는 다음과 같다.

우선 한 번 체크한 톱니바퀴는 또 체크하면 안 되기 때문에 (두 번 돌아감) 방문처리를 해주었다. 그래프에서 제일 중요한 방문처리 !!!

그러고 왼쪽에 있는 극성과 오른쪽에 있는 극성이 다른지 확인해 주었다. 어차피 톱니바퀴는 4개 있기 때문에 그 개수를 벗어나지 않는 선에서 분기처리 했다.

이때 중요한 게, DFS 재귀로 들어갈 때 방향에 -1을 곱해주어야 한다. 1번 톱니바퀴를 시계방향으로 돌리면, 2번 톱니바퀴는 반시계방향으로 돌아가기 때문이다. 그렇게 쭉 들어가다 모든 톱니바퀴를 방문하거나 톱니바퀴 인덱스를 넘어서면 그때 회전시켜 주고 함수를 빠져나오도록 구현했다.

DFS는 깊이탐색이기 때문에, 최대한 깊게 들어간 후 빠져나오는 게 포인트다.

 

원래 하나씩 체크하고 회전시키고 했는데, 이렇게 하면 나중 갈 때 회전시키기 어렵고, 중복 회전이 일어나게 된다. 때문에 회전하는 톱니바퀴를 모두 고려한 후, 회전시키는 게 훨씬 깔끔하다.

그리고 deque에서 제공하는 rotate를 사용하려고 했는데 초반 입력 코드를 list로 구현해 놔서 꼬였다.. 그래서 슬라이싱으로 구현했다. 주어진 값이 1차원이라면 deque의 rotate를 사용하는 게 훨씬 편할 거 같다.

 

 

정답 코드

import sys
input = sys.stdin.readline

def left_rotate(list):
  return list[1:] + list[:1] 

def right_rotate(list):
  return list[-1:] + list[:-1]

def rotate(tobni, number, direction):
    if direction == -1:
        tobni[number] = left_rotate(tobni[number])
    else:
        tobni[number] = right_rotate(tobni[number])

def dfs(number, direction, visited):
    visited[number] = True

    if number - 1 >= 0 and not visited[number - 1]:
        if tobni[number][6] != tobni[number - 1][2]:
            dfs(number - 1, (-1) * direction, visited)

    if number + 1 <= 3 and not visited[number + 1]:
        if tobni[number][2] != tobni[number + 1][6]:
            dfs(number + 1, (-1) * direction, visited)

    rotate(tobni, number, direction)

tobni = []
for _ in range(4):
    tobni.append(list(map(int, input().strip())))

k = int(input())
for _ in range(k):
    number, direction = map(int, input().split())
    visited = [False] * 4
    dfs(number - 1, direction, visited)

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

print(result)