문제 설명
•
수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초인지 구하는 문제
◦
수빈이가 이동할 수 있는 방향:
예제 입력/출력
•
입력1
5 17
Plain Text
복사
•
출력1
4
Plain Text
복사
제약 조건
•
◦
: 수빈이의 위치
◦
: 동생의 위치
문제 풀이
•
그래프 탐색을 이용하여 문제를 해결하면 된다. -
◦
노드의 개수가 N이고, 나올 수 있는 간선의 최대 개수는 3N
◦
BFS 알고리즘을 이용
풀이 코드
from collections import deque
MAX = 100_000
# Input
N, K = map(int, input().split())
# Init
q = deque()
q.append((N, 0)) # 수빈이가 있는 위치와 시간
visited = [False for _ in range(MAX + 1)]
# Solve (BFS)
while q:
x, t = q.popleft()
if x == K:
print(t)
exit()
for nx in [x - 1, x + 1, 2 * x]:
if (0 <= nx <= MAX) and not visited[nx]:
q.append((nx, t + 1))
visited[nx] = True
Python
복사