
정답
- 일자로 이어진 그래프에서 최단 경로를 찾는다고 생각하면 됨
- 최단 경로 == BFS
from collections import deque
n, k = map(int, input().split())
def BFS(n, k):
# 최대 점의 길이 + 1 (리스트는 0부터 시작하므로)
max_value = 100001
# 방문을 체크할 리스트
visited = [False] * max_value
# 최초 시작지점 (수빈이의 위치)부터의 거리를 담는 리스트
distance = [0] * max_value
queue = deque()
queue.append(n)
visited[n] = True
while queue:
current = queue.popleft()
# 현재 위치가 동생의 지점이라면, 수빈이의 지점부터 동생의 지점까지의 거리 반환
if current == k:
return distance[current]
# 현재 위치가 동생의 지점이 아니라면, 수빈이가 갈 수 있는 경우의 수 걷기, 뛰기를 적용하여 조건에 부합한다면 큐에 넣기
for next in (current - 1, current + 1, current * 2):
# 0이상, 100000이하이고 방문하지 않았다면
if next >= 0 and next < max_value and not visited[next]:
queue.append(next)
visited[next] = True
distance[next] = distance[current] + 1
print(BFS(n, k))
'Algorithm' 카테고리의 다른 글
1246 온라인 판매 / 그리디 (0) | 2025.05.26 |
---|---|
1302 베스트 셀러 / 해시맵 (0) | 2025.05.25 |
1012 유기농 배추 / DFS, BFS (0) | 2025.05.23 |
2468 안전 영역 / DFS, BFS (1) | 2025.05.22 |
2583 영역 구하기 / DFS, BFS (0) | 2025.05.21 |