[백준] 15662 톱니바퀴(2) [풀이 + 코드 + 해설]

구현  &  DFS & 재귀

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

15662번: 톱니바퀴 (2)

 

코드

import sys
from collections import deque
input = sys.stdin.readline


# 톱니바퀴 개수
t = int(input())
# T개의 톱니바퀴 받기
top = [deque(list(map(int, input().strip()))) for _ in range(t)]

# 회전수 
k = int(input())
# 회전할때마다 돌릴 번호와 & 방향
src = deque(tuple(map(int, input().strip().split())) for _ in range(k))


def dfs(number, direction, check):

    if check == "l":

        if right[number] == left[number-1]:
            return
        
        # 방향에 따라반대방향으로
        if direction == -1:
            top[number-1].rotate(1)
            direction = 1
        else:
            top[number-1].rotate(-1)
            direction = -1
            
        
        if number-1 == 0:
            return    
            
        dfs(number-1, direction, "l") 
        
        
           
    elif check == "r":

        if left[number] == right[number+1]:
            return
        
        # 방향에 따라반대방향으로
        if direction == -1:
            top[number+1].rotate(1)
            direction = 1
        else:
            top[number+1].rotate(-1)
            direction = -1

        if number+1 == t-1:
            return
        dfs(number+1, direction, "r")
        
        
        
    elif check == "first":
        if left[number] == right[number+1]:
            return
            
        # 방향에 따라반대방향으로
        if direction == -1:
            top[number+1].rotate(1)
            direction = 1
        else:
            top[number+1].rotate(-1)
            direction = -1
            
        if number+1 == t-1:
            return
        
        dfs(number+1, direction, "first")
        
        
        
    elif check == "last":
        if right[number] == left[number-1]:
            return
        
        # 방향에 따라반대방향으로
        if direction == -1:
            top[number-1].rotate(1)
            direction = 1
        else:
            top[number-1].rotate(-1)
            direction = -1


        if number-1 == 0:
            return 
    
        dfs(number-1, direction, "last")
        
        
        

while k > 0:
    left = [i[2] for i in top]
    right = [i[6] for i in top]
    
    d = src.popleft()
    
    # 회전해야되는 바퀴번호와, 그때의 방향
    num, dir = d[0], d[1]
    
    # 처음이든 중간이든 마지막이든
    # 회전시킬 바퀴가 처음 회전한다.
    if dir == -1:
        top[num-1].rotate(-1)
    else:
        top[num-1].rotate(1)
    
    
    # 처음 or 마지막
    if num-1 == 0 or num-1 == t-1:
    
        if num - 1 == 0:
            dfs(num-1, dir, "first")

        elif num -1 == t-1:
            dfs(num-1, dir, "last")

    else:
        # 구현
        # 왼, 오른쪽을 판단
        dfs(num-1, dir, "l")
        dfs(num-1, dir, "r")

    k-= 1
    
print(len([i[0] for i in top if i[0] == 1]))

 

설명

 해당 코드는 구현과 dfs or 재귀를 사용한 코드인데 사실 dfs라고 하는 게 맞을 것 같다. 그 이유는 아래에서 차근차근 설명합니다. 이번 문제는 약간 생각의 차이보다는 센스의 영역인 것 같다. 사실 늘 문해력이 좋다면 단번에 알아차리고 빠르게 풀어나가는 사람이 있었겠지만 난 반대였기 때문에 어떤 점에서 어려웠는지 그리고 어떤 점을 더 추가적으로 생각했어야 한 건지 설명해보려고 한다.

 

 문제의 핵심은 톱니바퀴를 '극에 따라서 바꿀지 말지 정하는 것' 이건 해당 문제를 읽어보면 알겠지만 극이 존재한다. N극과 S극 처음 코드를 예제케이스 3번, 5번을 두고 실패했었다. 그러다 시간이 좀 지나서 문제를 다시 읽어보고 이상한 점을 찾았다.

 

 

"톱니바퀴의 위치"

 

 

 톱니 바퀴의 위치를 잘못된 코드에서는 항상 2시 방향의 극만을 비교하고 있었던 것이다. 문제를 꼼꼼히 살펴보지 못했던 점이 크다. 또 주의해야 될 점이 한 가지 더 있다.

 

 

"처음과 마지막"

 

 

 처음과 마지막을 잘 살펴보면 처음은 오른쪽만 탐색하고 있는 걸 알 수 있고, 마지막은 왼쪽만 탐색하는 걸 알 수 있다. 만약 처음과 마지막을 나누지 않는다면 어떻게 될까? 당연히 인덱스 범위를 넘어서게 된다. 그렇기 때문에 처음과, 마지막을 나눠 구현하면 구분을 줄 수 있기 때문에 가능하다. 그럼 처음과 마지막을 제외한 나머지 부분만 구현해 주면 된다. 처음과 나머지 부분을 제외한 부분이라면 가운데 부분이라고 생각해 볼 수 있다. 이 가운데 부분은 처음과 마지막을 돌리는 것과는 달리 왼쪽 오른쪽을 둘 다 탐색해야 한다.

 그럼 전체적인 구현 방법은 정해졌다. 디테일한 구현 내용을 몇가지 살펴보자면 위에서 언급했듯, "톱니바퀴의 위치"를 참조하는 방향은 기준이 되는 곳을 보고 판단해야 된다는 것이다. 예를 들어 3번 톱니바퀴를 바꾼다고 했을 때(4개까지 있다고 가정하자.) 3번의 위치는 중간에 위치에 해당한다. 따라서 왼쪽, 오른쪽 전부 탐색해야 하며, 왼쪽을 탐색할 때는 기준점은 3번을 기준으로 3번 톱니바퀴는 톱니바퀴의 6번 위치를 참조해야 하고 3번과 비교할 왼쪽 2번은 톱니바퀴의 2번 위치를 참조해야 한다. 그래야만 톱니바퀴의 위치를 고려한 구현이기 때문이며 정답과 이어질 수 있기 때문이다. 오른쪽도 마찬가지로 똑같이 생각해 보면 방향만 바꿔준다면 가능한 구현이라는 걸 알 수 있다.

 한가지 더 알아보자면 "left, right를 처음 초기화한 기준으로 봐야 된다는 것이다." 만약 바꿀때 마다 톱니바퀴의 위치를 참조해 버리면 어떤 경우가 발생될까? 당연히 "극이 바뀐 상태에서 톱니바퀴의 위치를 보게 된다." 하지만 문제에서 요구하는 의도는

 

 

"처음 상태에서 극을 바라봤을 때"

 

 

 문제 그림을 보면 단번에 이해가 갈 수 있다. 그렇기 때문에 모든 구현이 완성된 다음 더 이상 돌려야 할 톱니바퀴가 없다면 깊이 우선 탐색이 종료되고 이후에 변경된 위치를 초기화해 주면 의도대로 구현이 가능하게 된다.

 

 

"따라서 왼쪽이든 오른쪽이든 톱니바퀴는 연결되어 있기 때문에 연결된 곳을 끝까지 탐색한다는 점에서

깊이 우선 탐색이라고 할 수 있다."