- 수빈이의 위치 : N (0<=N<=100,000)
- 동생의 위치 : K (0<=K<=100,000)
- 걸을 때 : X-1 or X+1
- 순간이동할 때 : 2*X
- N ➡️ K까지 걸리는 가장 빠른 시간은?
🔍 코드
from collections import deque
n, k = map(int, input().split())
#움직일 수 있는 최대 좌표는 100000
max = 100000
# 해당위치에 도착했을 때 시간을 표시하는 리스트
visited = [0] * (max + 1)
def bfs():
q = deque()
q.append(n)
while q:
x = q.popleft()
if x == k:
print(visited[x])
break
for j in (x-1, x+1, x*2):
# 주어진 범위 내에 있고 아직 방문하지 않았다면
if 0<= j <= max and not visited[j]:
visited[j] = visited[x] + 1
q.append(j)
bfs()
📌 코드 풀이
- 이 문제는 이전의 미로탐색 문제와 비슷하다. 미로탐색에서는 2차원배열의 맵이었다면 이 문제는 1차원상의 좌표에서 이동한다.
- BFS(너비 우선 탐색)알고리즘을 사용하여 해결한다.
- 방문한 위치를 체크하기 위한 리스트
visited를 생성한다.
왜 DFS가 아닌 BFS를 사용?
예를 들어, 동생의 위치는 1, 수빈이의 위치는 2일때 수빈이가 동생의 위치까지 가는 가장 빠른 시간을 구한다고 하자.
이때 우선 한 칸 앞으로 이동하며 탐색한다고 했을 때, DFS를 사용하면 (2, 3, 4, 5, ... 100,000)까지 탐색한 후에야 뒤로 한 칸 이동하는 탐색을 시작한다.
만약 뒤로 한 칸 이동하는 탐색부터 했다면 빠르게 바로 찾을 수 있었겠지만 위의 상황처럼 찾고자 하는 방향에 노드가 없을 때는 너무 깊이 빠질 수 있다는 위험이 존재한다. (DFS로는 시간초과 발생)
하지만, BFS는 현재 위치에서 +1, -1, 2모두 시도해본 뒤 다음으로 넘어가기 때문에 DFS보다 빠르게 정답을 찾을 수 있다.
BFS는 그물망처럼 +1, -1, 2만큼 퍼져나가며 최적의 해를 찾기 때문에 안정적인 시간 내에 정답을 찾을 수 있다.
따라서 최단 경로, 최단 횟수를 구할때는 BFS가 유리하다. BFS는 가장 처음 발견되는 해답이 최단거리다!
💫 Comment
bfs를 사용해야 함은 알았지만 내 힘으로는 안풀려서 결국 정답코드를 봤다ㅜ
방문을 체크하고 범위내에 있음을 체크하는건 생각하지 못했다.
-
내가 생각한 방법 :
걸리는 시간(누적 초)을 함께 큐에 넣었다.q.append(현재위치, 현재누적초)(이 방법을 사용한 코드)
하지만 이 경우 큐에 누적된 초도 저장해야하고 방문한 위치도 따로 체크해야함. 방문한 위치를 체크하는 리스트visited에 누적 초도 함께 저장하면 더욱 효율적임. -
왜 방문을 체크? : 이미 계산된 내용을 중복으로 또 처리할 필요는 없으므로.
