수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있음
수빈이는 걷거나 순간이동 가능
만약, 수빈이의 위치가 X일 때걷는다면1초 후에X-1 또는 X+1로 이동
순간이동을 하는 경우에는 1초 후에2*X의 위치로 이동
수빈이와 동생의 위치가 주어졌을 때,수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지구하기
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어짐
N과 K는 정수
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력
시간 제한: 2초
메모리 제한: 128 MB
"""
입출력 예시)
5 17
-> 4
"""
# N = 5, K = 17
# -> 수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있음
# => 4
## 의사코드 ##
# 가장 빠른 시간 -> 최단 경로 찾기 => BFS
# deque
# 수빈이 위치: N
# 동생 위치: K
# 수빈이가 이동할 수 있는 곳
# 1) X - 1
# 2) X + 1
# 3) 2 * X
# N+1만큼의 배열(visited) 생성
# visited = [0] * (N+1)
# BFS
# while q:
# 현재 위치 = q.popleft()
# if 현재 위치 == K: # K -> 동생 위치
# reutrn visited[현재 위치]
# # 수빈이가 이동할 수 있는 위치 내에서 탐색
# for 다음 위치 in ((현재 위치 -1), (현재 위치 +1), (2*현재 위치)):
# if 0 <= 다음 위치 < (N+1) and not visited[다음 위치]:
# visited[다음 위치] = visited[현재 위치] + 1 # 방문처리 & 시간+1
# q.append(다음 위치)
첫 번째 시도
from collections import deque
# 수빈이 위치, 동생 위치
n, k = map(int, input().split())
# n+1 만큼의 배열(visited) 생성
visited = [0] * (n+1)
# BFS 수행
def bfs():
q = deque([n])
while q:
current_pos = q.popleft()
if current_pos == k:
return visited[current_pos]
# 수빈이가 이동할 수 있는 위치 내에서 탐색
for next_pos in (current_pos-1, current_pos+1, 2*current_pos):
# 다음 위치가 그래프의 범위를 벗어나지 않으면서 아직 방문하지 않았다면
if 0 <= next_pos < (n+1) and not visited[next_pos]:
# 방문처리 & 걸리는 시간 + 1
visited[next_pos] = visited[current_pos] + 1
q.append(next_pos)
print(bfs())
-> 틀림 (값이 return 되지 않음)
-> visited의 길이를 n과 k의 최댓값만큼 설정해야 하는데 그냥 n+1 값으로 설정해서 틀림
(n=5 -> visited의 길이가 6으로만 설정된 것)
통과한 코드
from collections import deque
# 수빈이 위치, 동생 위치
n, k = map(int, input().split())
# n+1 만큼의 배열(visited) 생성
max_n = 100000
visited = [0] * (max_n+1)
# BFS 수행
def bfs():
q = deque([n])
while q:
current_pos = q.popleft()
if current_pos == k:
return visited[current_pos]
# 수빈이가 이동할 수 있는 위치 내에서 탐색
for next_pos in (current_pos-1, current_pos+1, 2*current_pos):
# 다음 위치가 그래프의 범위를 벗어나지 않으면서 아직 방문하지 않았다면
if 0 <= next_pos < (max_n+1) and not visited[next_pos]:
# 방문처리 & 걸리는 시간 + 1
visited[next_pos] = visited[current_pos] + 1
q.append(next_pos)
print(bfs())
-> visited를 생성할 때 N과 K의 최대값인 100000 만큼을 따로 변수로 설정
BFS로 탐색을 진행할 때
기본 BFS의 소스코드에서 탐색할 범위를 수빈이가 이동할 수 있는 범위로 어떻게 수정해야 할지가 바로 떠오르지 않았다.
