✅톱니바퀴 (골드 5)

문제 출처 : https://www.acmicpc.net/problem/14891

14891번: 톱니바퀴

 

#1. 설계 및 풀이

 

1. 해당 톱니바퀴를 prev, 영향을 줄 수 있는 톱니바퀴를 next (prev-1, prev+1)라고 할 때,

범위가 1부터 4이고, visited가 0이면 

prev < next : prev[2] == prev[6]을 조사하고 다르면 재귀함수 호출 후 회전 수행

prev > next : prev[6] == prev[2]를 조사하고 다르면 재귀함수 호출 후 회전 수행

 

2. 회전하는 함수 만들기

 

# 톱니바퀴

import sys
input = sys.stdin.readline

def turn_topnis(arr, d) :
    if d == 1 : # 시계
        return [arr[-1]] + arr[:-1]
    else : # 반시계
        return arr[1:] + [arr[0]]

def dfs(num, d) :
    for candi in [num-1, num+1] :
        if candi <= 0 or candi > 4 :
            continue
        
        if visited[candi] != 0 :
            ## 주의 !! 여기서 return 해버리면 남은 candi는 시도해보지도 못하고 끝난다.
            continue

        if num < candi :
            if topnis[num-1][2] == topnis[candi-1][6] :
                continue
            visited[candi] = 1
            dfs(candi, -d)
            topnis[candi-1] = turn_topnis(topnis[candi-1], -d)

        else :
            if topnis[num-1][6] == topnis[candi-1][2] :
                continue
            visited[candi] = 1
            dfs(candi, -d)
            topnis[candi-1] = turn_topnis(topnis[candi-1], -d)

topnis = [list(map(int, list(input().rstrip()))) for _ in range(4)]

for _ in range(int(input())) : # k번 회전
    visited = [0] * 5
    num, d = map(int, input().split())
    visited[num] = 1
    dfs(num, d)
    topnis[num-1] = turn_topnis(topnis[num-1], d)
    
score = [1, 2, 4, 8]
answer = 0
for i in range(4) :
    if topnis[i][0] != 0 :
        answer += score[i]

print(answer)

 

- 코드를 최대한 짧게 작성하려고 했다.

for문이나 if문이 중첩되지않게 중간에 continue로 처리했다.

 

처음엔 continue 대신 return을 호출해 결과값이 이상하게 나왔는데,

return을 호출해버리면 나머지 candi에 대해서는 조사하지 않고 함수를 종료시키기 때문에 주의해야한다 !!

 

- 시뮬레이션 문제는 문제를 정확히 이해해서 구현하는 것도 어렵지만

문제가 복잡하다보니 디버깅에서 에러를 잡을 때 막막한 경우가 많은 것 같다.

 

순서도를 작성하고, 꼼꼼히 설계하고, 시간복잡도도 계산하고

복잡한 부분은 손코딩까지 마치고 예제케이스를 대입해봤을 때 문제가 없어서

실제로 구현하고 코드를 돌려보면 어디서 났는지 모를 에러들이 발생했다.

 

이 에러들을 잡을 때 하나하나 디버깅해야해서 굉장히 복잡하고 막막하고 시간도 오래걸렸는데

모두 구현하고 에러를 잡으려고 하기보다는

최대한 모듈별로 쪼개서 결과값을 출력하고 확인해나가면서 풀어봐야겠다.

 

 

- 이전에는 촉박한 시간때문에 조급해서 문제를 제대로 이해하지도 않고

설계도 대충하고 코드를 짜다보니 구현에서 막히는 부분이 많았었는데,

 

순서도를 꼼꼼히 작성하고,

복잡한 부분은 직접 손코딩하면서 어떻게 돌아가는지, 어떻게 짜야할지 틀을 잡고나니까 훨씬 수월했다.

 

 

이런 시뮬레이션 문제들을 많이 풀어보고 익숙해져야겠다.

포기하지말자 파이팅 !

 

 

#2. 개선할 점

 

- BFS로도 풀 수 있다.

재귀가 막막하고 오래걸릴 것 같은데 BFS로도 풀 수 있다면 그 방법도 생각해보자.