백준 파이썬 14891 톱니바퀴

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

14891번: 톱니바퀴

 

간만에 정말 재밌게 풀었던 문제였습니다.

 

기본적으로 DFS를 사용해서 문제풀이를 진행하였습니다.

 

target과 direction을 정하고나서

해당 target에 연관된 모든 톱니바퀴를 dfs를 통해서 위치변환을 마치고 마지막으로

처음 정한 target의 톱니바퀴를 변경시켜 문제풀이를 하였습니다. 

 

from collections import deque

wheel = []

for i in range(4):
    wheel.append(deque(list(map(int, input()))))

TC = int(input())

def dfs(target, direction):

    visited[target] = 1

    if direction == -1:
        if 0 <= target - 2 and visited[target-1] == 0:
            if wheel[target - 1][6] != wheel[target - 2][2]:
                dfs(target - 1, 1)
                wheel[target - 2].appendleft(wheel[target - 2].pop())

        if target < 4 and visited[target+1] == 0:
            if wheel[target - 1][2] != wheel[target][6]:
                dfs(target + 1, 1)
                wheel[target].appendleft(wheel[target].pop())

    if direction == 1:
        if 0 <= target - 2 and visited[target-1] == 0:
            if wheel[target - 1][6] != wheel[target - 2][2]:
                dfs(target - 1, -1)
                wheel[target - 2].append(wheel[target - 2].popleft())

        if target < 4 and visited[target+1] == 0:
            if wheel[target - 1][2] != wheel[target][6]:
                dfs(target + 1, -1)
                wheel[target].append(wheel[target].popleft())

for i in range(TC):
    target, direction = map(int, input().split())
    visited = [0 for _ in range(5)]

    dfs(target, direction)

    if direction == -1:
        wheel[target - 1].append(wheel[target - 1].popleft())
    else:
        wheel[target-1].appendleft(wheel[target-1].pop())

result = 0

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

print(result)