[코딩테스트, 더 이상 미룰 수 없다] BOJ 14891 - 구현, 실행의 판단 파트와 실제 실행파트 구분하기

판단과 실행을 분리해야 한다는 점을 깨닫기까지

 

 

이 문제에서 “1번 톱니를 회전시킨다”는 말은
1번 톱니를 회전의 시작점으로 삼는다는 뜻에 가깝다.

즉 실제 동작 순서는 다음과 같다.

1. 현재 상태를 기준으로 인접한 톱니끼리 맞닿은 극을 비교한다.
2. 어떤 톱니가 어느 방향으로 회전할지 결정한다.
3. 회전 여부가 모두 결정된 뒤, 실제 회전을 한꺼번에 적용한다.

핵심은 비교는 현재 상태로 하고, 회전은 나중에 한다는 점이다.

---

왜 바로 회전하면 안 되는가

처음에는 DFS로 인접 톱니를 타고 들어가면서 바로 회전시키면 될 것 같았다.
하지만 이 방식에는 문제가 있다.

예를 들어 1번 톱니를 먼저 회전시켜 버리면, 1번 톱니의 배열이 바뀐다.
그러면 그 다음에 2번 톱니와의 접점을 비교할 때는 원래 상태가 아니라 이미 회전된 상태를 기준으로 비교하게 된다.

하지만 문제는 회전 전 상태를 기준으로 연쇄 회전 여부를 판단해야 한다.
즉, DFS를 쓰더라도 다음과 같이 해야 한다.

• DFS에서는 실제 회전을 하지 않는다.
• 각 톱니가 회전해야 하는지, 회전한다면 어느 방향인지 rotate 배열에 기록만 한다.
• DFS가 끝난 뒤 rotate 배열을 바탕으로 실제 회전을 적용한다.

판단 단계와 실행 단계를 분리해야 하는 시뮬레이션 문제가 있다는 사실을 알게 되었다.

---

이 문제를 통해 정리한 기준

이 문제를 이해하면서 자연스럽게 하나의 기준도 생겼다.

지금 상태를 바꾸면, 아직 처리하지 않은 다른 대상의 판단 기준이 바뀌는가?

이 질문에 대한 답이 “그렇다”라면, 판단과 실행을 분리해야 할 가능성이 높다.

톱니바퀴 문제는 여기에 정확히 해당한다.

• 한 톱니를 먼저 돌려 버리면
• 그 톱니의 2번, 6번 위치 값이 달라지고
• 그 결과 다음 톱니의 회전 여부 판단이 바뀔 수 있다

그래서 이 문제는 반드시 다음 구조를 따라야 한다.

• 회전 여부 판단
• 회전 방향 기록
• 마지막에 한꺼번에 회전

---

회전 방향을 기록하는 rotate 배열

이 문제를 구현할 때 중요한 도구가 회전 방향을 기록하는 배열이다.

예를 들어 톱니가 4개라면 다음처럼 둘 수 있다.

rotate = [0] * 4

각 값의 의미는 다음과 같다.

• 0: 회전하지 않음
• 1: 시계 방향 회전
• -1: 반시계 방향 회전

예를 들어 rotate = [1, -1, 1, 0] 이라면

• 1번 톱니는 시계 방향
• 2번 톱니는 반시계 방향
• 3번 톱니는 시계 방향
• 4번 톱니는 회전하지 않음

이라는 뜻이다.

이 배열을 두면 DFS에서는 회전 방향만 결정하면 되고,
모든 탐색이 끝난 후 실제 회전은 따로 처리할 수 있다.

---

DFS로 회전 전파를 확인하는 방식

이 문제는 톱니가 1차원으로 연결되어 있기 때문에 꼭 DFS가 필요한 것은 아니다.
왼쪽으로 한 번, 오른쪽으로 한 번 훑는 방식으로도 충분히 풀 수 있다.

하지만 “회전이 인접한 톱니로 전파된다”는 구조만 보면 DFS로도 충분히 표현할 수 있다.
다만 중요한 점은 DFS 안에서 실제 회전을 하면 안 된다는 것이다.

DFS의 역할은 다음과 같다.

1. 현재 톱니의 회전 방향을 rotate[idx]에 기록한다.
2. 왼쪽 톱니와 맞닿은 극이 다르면, 반대 방향으로 DFS를 호출한다.
3. 오른쪽 톱니와 맞닿은 극이 다르면, 반대 방향으로 DFS를 호출한다.

즉 DFS는 전파 여부를 확인하는 용도로만 쓰인다.

---

접점을 비교하는 기준

문제에서 인접 톱니끼리 비교해야 하는 위치는 고정되어 있다.

• 현재 톱니의 오른쪽 접점: 인덱스 2
• 왼쪽 톱니의 왼쪽 접점: 인덱스 6

그래서

• 왼쪽 톱니와 비교할 때는 gears[idx][6] 과 gears[left][2]
• 오른쪽 톱니와 비교할 때는 gears[idx][2] 와 gears[right][6]

을 비교하게 된다.

극이 다르면 회전이 전파되고, 같으면 전파가 끊긴다.

---

구현 코드

아래는 위의 사고를 그대로 반영한 DFS 방식의 구현이다.

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

gears = [deque(input().strip()) for _ in range(4)]
k = int(input())

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

    left = idx - 1
    right = idx + 1

    if left >= 0 and not visited[left]:
        if gears[idx][6] != gears[left][2]:
            dfs(left, -direction, visited, rotate)

    if right < 4 and not visited[right]:
        if gears[idx][2] != gears[right][6]:
            dfs(right, -direction, visited, rotate)

for _ in range(k):
    num, direction = map(int, input().split())
    num -= 1

    visited = [False] * 4
    rotate = [0] * 4

    dfs(num, direction, visited, rotate)

    for i in range(4):
        if rotate[i] != 0:
            gears[i].rotate(rotate[i])

score = 0
for i in range(4):
    if gears[i][0] == '1':
        score += (1 << i)

print(score)

---

이 문제를 통해 얻은 정리

 

처음에는 단순히 “어떻게 회전하지?”에 집중했다면,
풀고 나서는 “언제 상태를 바꾸면 안 되는가?”를 생각하게 되었다.

이 감각은 톱니바퀴 문제 하나에만 필요한 것이 아니다.
시뮬레이션 문제 전반에서 매우 자주 등장하는 사고 방식이다.

예를 들어

• 이번 상태를 기준으로 다음 상태를 만들어야 하는 문제
• 동시에 여러 대상이 변하는 문제
• 순서대로 처리하면 결과가 달라질 수 있는 문제

 

에서는 대부분 같은 고민이 필요하다.

그런 점에서 이 문제는 단순 구현 문제라기보다는,
시뮬레이션 문제에서 판단과 실행을 어떻게 분리해서 생각해야 하는지를 훈련하게 해주는 문제였다.