금지된 위치를 나타내는 배열 forbidden이 있다고 가정해 보겠습니다. 여기서 forbidden[i]는 벌레(bug)가 해당 위치로 점프할 수 없음을 의미하며, 추가로 세 값 a, b, x가 주어집니다. 벌레의 집은 수직선 위의 위치 x에 있고, 벌레는 처음에 위치 0에서 출발합니다. 벌레는 아래 규칙에 따라 점프할 수 있습니다.
- 정확히 a만큼 앞쪽(오른쪽)으로 점프할 수 있습니다.
- 정확히 b만큼 뒤쪽(왼쪽)으로 점프할 수 있습니다.
- 뒤로 두 번 연속해서 점프할 수 없습니다.
- 배열에 지정된 금지된 위치로는 점프할 수 없습니다.
- 집보다 더 앞쪽 위치까지는 점프할 수 있지만, 음수 위치로는 점프할 수 없습니다.
우리는 벌레가 목적지인 집에 도달하기 위해 필요한 최소 점프 횟수를 구해야 하며, 도달이 불가능한 경우에는 -1을 반환해야 합니다.
예를 들어 입력이 forbidden = [2,3,7,9,12], a = 4, b = 2, x = 16이라면 출력은 7이 됩니다. 그 과정은 다음과 같습니다. 0에서 출발해 a = 4씩 두 번 앞으로 점프하여 4와 8에 도달하지만, 12는 금지된 위치이므로 건너뛸 수 없습니다. 대신 b = 2만큼 뒤로 물러나 6에 도착한 뒤, 10 → 14 → 18로 점프하고 다시 두 번 뒤로 점프하여 16에 도달합니다. 따라서 총 7번의 점프가 필요합니다.
해결 접근 방법
이 문제는 너비 우선 탐색(BFS)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 방향을 뒤집어 x에서 출발해 0에 도달하는 문제로 변환하는 것입니다. 단계별 풀이 과정은 다음과 같습니다.
- 큐를 생성하고 (x, 0, True) 튜플을 삽입합니다. forbidden 리스트는 조회 속도를 높이기 위해 집합(set)으로 변환합니다.
- 탐색 상한값 lim := a + b + max(x, forbidden의 최댓값)으로 설정합니다.
- 큐가 빌 때까지 다음을 반복합니다.
- (curr, jumps, is_b) := 큐의 첫 번째 요소를 꺼냅니다.
- curr가 forbidden에 포함되거나 0 ≤ curr ≤ lim 조건을 만족하지 않으면 다음 반복으로 넘어갑니다.
- curr를 forbidden에 추가하여 방문 처리합니다.
- curr가 0이면 jumps를 반환합니다.
- is_b가 True이면 (curr + b, jumps + 1, False)를 큐에 삽입합니다.
- (curr - a, jumps + 1, True)를 큐에 삽입합니다.
- 반복이 종료되면 -1을 반환합니다.
예시 코드
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
def solve(forbidden, a, b, x):
queue, forbidden = [(x,0,True)], set(forbidden)
lim = max(max(forbidden),x)+a+b
while queue:
curr,jumps,is_b = queue.pop(0)
if curr in forbidden or not 0 <= curr <= lim:
continue
forbidden.add(curr)
if curr==0:
return jumps
if is_b:
queue.append((curr+b,jumps+1,False))
queue.append((curr-a,jumps+1,True))
return -1
forbidden = [2,3,7,9, 12]
a = 4
b = 2
x = 16
print(solve(forbidden, a, b, x))입력
[2,3,7,9, 12], 4, 2, 16출력
7