생각해봅시다!

• 한주 전에 이런 문제 (동전 2)를 푼 적이 있었는데요, 그래프 문제처럼 안 보였지만 BFS로 해결이 가능한 문제였습니다.
• 이 문제도 마찬가지로 BFS 문제로 생각해서 풀 수 있습니다.

BFS로 해석하기

• 이런 문제를 풀 땐 항상 현재 상태는 노드로, 상태의 변화는 간선으로 생각합니다.
• 노드는 (돌 번호, 현재 점프속도) 형태로 구성하고, 간선은 점프를 통해 다른 돌로 넘어가는 행위로 생각해봅시다.
  • 현재 점프속도가 x일 때, 속도를 줄여 x-1칸 / 속도를 유지해 x칸 / 속도를 늘려 x + 1칸 점프를 할 수 있습니다. 각각 경우가 간선으로 연결되어 있다고 생각하면 됩니다.
  • 현재 점프속도에 따라 이후 방문할 수 있는 돌이 달라지므로, 점프속도도 노드의 상태에 포함되어야 합니다.
• 우리가 찾는 돌 번호의 노드를 방문할 때까지 BFS를 계속 진행합니다.
• 가까운 노드부터 탐색하는 BFS 특성상, 탐색하는 과정에서 최소한의 간선(즉 점프)로 도달하는 경로를 찾게 됩니다.
  • 이 점을 이용해 특정 돌에 도달하는데 필요한 점프의 최소 횟수를 구할 수 있습니다.
  • 대신 지금까지 거친 간선 수를 어딘가에 저장은 해 둬야겠죠.

입력 받기

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

# 돌의 수 (N), 방문할 수 없는 돌의 수 (M)
N, M = map(int, input().split())

# 이미 확인한 노드 - (돌번호, 점프속도)를 저장할 집합
checked = set()

# 방문할 수 없는 돌 번호를 저장할 집합
banned = set()

for _ in range(M):
    banned.add(int(input()))

• BFS 쓸 꺼니 deque를 사용합니다.
• 이미 확인한 노드는 (돌번호, 점프속도) 형태로 checked 집합에 저장해, 중복 방문을 방지합니다.
• 방문할 수 없는 돌번호는 banned 집합에 저장합니다.
• 집합에 특정 원소가 있는지 확인하는데는 약 $O(1)$의 시간 복잡도가 소요되므로 시간 효율적이라고 볼 수 있겠죠.

BFS 구현

# (돌 번호, 점프속도, 점프 횟수)
queue = deque([(1, 0, 0)])
checked.add((1, 0))

• 큐 queue에는 각 노드를 (돌 번호, 점프속도) 형태로 저장합니다.
  • 추가로 현재 노드에 도착하는 데 필요한 점프 횟수 (즉 거치는 간선 수)도 저장합니다.
• 시작 지점은 1번 돌이며, 앞으로 한 칸밖에 점프하지 못하므로 속도는 0이며, 점프 횟수도 아직 0회이므로 (1, 0, 0)을 푸시해줍니다.
• 1번 돌, 점프속도 0에 해당하는 노드 (1, 0)을 checked 집합에 더해줍니다.

🤔왜 맨 처음에 점프 속도는 0인가요?

• 본 문제에서는 현재 속도가 x일 때 감속해 x-1칸 점프하거나, 속도를 유지해 x칸 점프하거나, 가속해 x+1칸 점프할 수 있다고 합니다.
• 이때 제일 먼저 점프를 할 때에는 한 칸밖에 점프하지 못한다, 그리고 점프를 할 땐 한 칸 이상씩 해야 한다는 제한이 있습니다.
• x가 0일 때 -1칸, 0칸 점프는 불가능하므로, 첫 점프는 1칸만 가능합니다.
• 이런 이유로 시작 점프 속도를 0으로 두어, 첫 점프가 무조건 1칸이 되게 합니다.

def bfs():
    while queue:
    	# 노드 맨 앞의 (돌 번호, 점프속도, 점프 횟수) 꺼내기
        i, jump, dist = queue.popleft()
        
        # 목적지에 도착한 경우, 점프 횟수 반환
        if i == N:
            return dist

		# 속도-1 / 속도유지 / 속도+1 하는 경우 탐색
        for offset in [-1, 0, 1]:
            new_jump = jump + offset	# 새로운 점프 속도 (다음에 점프할 칸 수)
            if new_jump < 1:			# 적어도 1칸 이상을 점프해야 함
                continue
            j = i + new_jump			# 점프 이후 도착하는 돌번호
            
            # 도착한 돌 번호가 N 이하인가?
            # 올라갈 수 없는 돌이 아닌가?
            # 이미 방문한 (돌 번호, 점프속도) 조합이 아닌가?
            if j <= N and j not in banned and (j, new_jump) not in checked:
            	# 그러면 queue / checked에, 점프 수를 1 더해서 삽입
                queue.append((j, new_jump, dist + 1))
                checked.add((j, new_jump))
            
    # 목적지에 도달하지 못할 때
    return -1

• 매번 (i: 돌 번호, jump: 점프 속도, dist: 점프 수)를 큐에서 꺼내 현재 상태를 확인하고, (노드 꺼내기)
  • 속도를 1 줄이는 경우 / 유지하는 경우 / 1 가속하는 경우를 탐색합니다 (인접 노드 탐색)
  • 단, 적어도 1칸 이상 점프를 해야 하므로, 속도가 1 미만인 경우 (if new_jump < 1)는 무시합니다.
• 이후 도착한 돌 번호가 $N$ 이하인지, banned에 포함된 올라갈 수 없는 돌은 아닌지 확인합니다.
  • 또한 BFS문제인 만큼 이미 방문한 노드가 아닌지도, checked 집합에서 확인합니다.
  • 위 조건을 만족하면 queue에 삽입하고 checked에 더해 줍니다. (방문 처리)
• 도중에 목적지 $N$에 도착하면, 점프 수를 반환합니다.
  • 도착하지 못하고 BFS가 종료되면, -1을 반환합니다.

풀이

# (돌 번호, 점프속도, 점프 수)
queue = deque([(1, 0, 0)])
checked.add((1, 0))

def bfs():
    while queue:
    	# 노드 맨 앞의 (돌 번호, 점프속도, 점프 수) 꺼내기
        i, jump, dist = queue.popleft()
        
        # 목적지에 도착한 경우, 점프 수 반환
        if i == N:
            return dist

		# 속도-1 / 속도유지 / 속도+1 하는 경우
        for offset in [-1, 0, 1]:
            new_jump = jump + offset	# 새로운 점프 속도 (다음에 점프할 칸 수)
            if new_jump < 1:			# 적어도 1칸 이상을 점프해야 함
                continue
            j = i + new_jump			# 점프 이후 도착하는 돌
            
            # 도착한 돌 번호가 N 이하인가?
            # 올라갈 수 없는 돌이 아닌가?
            # 이미 방문한 (돌 번호, 점프속도) 조합이 아닌가?
            if j <= N and j not in banned and (j, new_jump) not in checked:
            	# 그러면 queue / checked에, 점프 수를 1 더해서 삽입
                queue.append((j, new_jump, dist + 1))
                checked.add((j, new_jump))
                
    return -1

시간 복잡도

• 금지된 돌 $M$개를 집합에 추가하는 과정에서 $O(M)$
• BFS 과정에서 최대 $N^2$개의 노드를 탐색 (돌 $N$개, 점프 속도 $1$~$N$) -> $O(N^2)$
  • 하지만 실제로는 점프 속도가 너무 크면 곧바로 범위를 벗어나거나, 도달할 수 없는 상태가 많아 대부분의 상태는 탐색되지 않음

기억할 점

• 현재 상태를 노드로, 상태의 변화를 간선으로, 최소/최단의 정답 조건을 최단 거리로 생각하면, 전혀 다른 유형의 문제도 BFS로 바꿔 풀 수 있다