파이썬으로 목표 지점까지 도달하는 최소 이동 횟수 구하기 (DFS 풀이)

문제 개요

1차원 도로 위를 달리는 자동차가 있다고 가정해 봅시다. 자동차의 현재 위치(position)는 0이며, 초기 속도(speed)는 1입니다. 이때 다음 두 가지 연산 중 하나를 선택해 수행할 수 있습니다.

가속(Acceleration): position := position + speed, speed := speed × 2
후진 기어(Reverse Gear): speed가 양수면 speed := −1, 그렇지 않으면 speed := 1

목표 지점(target)에 정확히 도달하기 위해 필요한 최소 이동 횟수를 구하는 것이 이 문제의 목표입니다.

예를 들어 target = 10이 입력으로 주어지면, 정답은 7이 됩니다.

접근 방법: 깊이 우선 탐색(DFS)

연속된 가속을 하나의 묶음으로 생각하면 문제가 단순해집니다. k번 연속 가속 시 이동 거리는 2^k − 1이 되므로, 각 자릿수(digit)별 가속 묶음을 전진·후진 방향에 배치하는 모든 경우를 DFS로 탐색하되, 이미 찾은 최솟값(ans)보다 비용이 커지는 경로는 가지치기(pruning)하여 탐색 범위를 줄입니다.

dfs() 함수의 동작 단계

dfs(digit, cost, pos, neg, target) 형태로 함수를 정의합니다. pos와 neg는 각각 전진·후진 가속 묶음의 개수입니다.
현재까지의 총비용 tot = cost + max(2 × (pos − 1), 2 × neg − 1)을 계산합니다. 이는 방향 전환에 필요한 추가 이동 수까지 반영한 값입니다.
tot가 이미 구한 답(ans) 이상이면 더 탐색하지 않고 즉시 반환합니다.
target이 0이면 ans를 min(ans, tot)으로 갱신한 뒤 반환합니다.
step = 2^digit − 1을 계산합니다. 해당 자릿수의 가속 묶음이 만들어내는 이동 거리입니다.
step × 2 < |target|이면 남은 거리를 커버할 수 없으므로 반환합니다.
다음 다섯 가지 분기로 재귀 호출을 진행합니다.
- 이 자릿수를 사용하지 않는 경우: dfs(digit − 1, cost, pos, neg, target)
- 전진 가속 1묶음 사용: dfs(digit − 1, cost + digit, pos + 1, neg, target − step)
- 전진 가속 2묶음 사용: dfs(digit − 1, cost + digit × 2, pos + 2, neg, target − step × 2)
- 후진 가속 1묶음 사용: dfs(digit − 1, cost + digit, pos, neg + 1, target + step)
- 후진 가속 2묶음 사용: dfs(digit − 1, cost + digit × 2, pos, neg + 2, target + step × 2)

메인 함수의 처리 순서

ans를 무한대에 가까운 아주 큰 값으로 초기화합니다.
hi = 1부터 시작해 2^hi ≥ target이 될 때까지 hi를 증가시켜 필요한 최대 자릿수를 구합니다.
dfs(hi, 0, 0, 0, target)을 호출해 탐색을 시작합니다.
탐색이 끝나면 ans를 반환합니다.

구현 예제

class Solution:
    def solve(self, target):
        self.ans = int(1e9)
        hi = 1
        while (1 << hi) < target:
            hi += 1
        self.dfs(hi, 0, 0, 0, target)
        return self.ans

    def dfs(self, digit, cost, pos, neg, target):
        tot = cost + max(2 * (pos - 1), 2 * neg - 1)
        if tot >= self.ans:
            return
        if target == 0:
            self.ans = min(self.ans, tot)
            return
        step = (1 << digit) - 1
        if step * 2 < abs(target):
            return
        self.dfs(digit - 1, cost, pos, neg, target)
        self.dfs(digit - 1, cost + digit, pos + 1, neg, target - step)
        self.dfs(digit - 1, cost + digit * 2, pos + 2, neg, target - step * 2)
        self.dfs(digit - 1, cost + digit, pos, neg + 1, target + step)
        self.dfs(digit - 1, cost + digit * 2, pos, neg + 2, target + step * 2)


ob = Solution()
print(ob.solve(10))

실행 결과

입력:

출력:

마무리

이 풀이의 핵심은 가속을 2의 거듭제곱 단위 묶음으로 분해하고, 방향 전환에 드는 추가 비용까지 상태에 포함해 탐색한다는 점입니다. 가지치기를 활용해 불필요한 경로를 조기에 차단하므로, target이 커져도 실용적인 시간 안에 최소 이동 횟수를 구할 수 있습니다.