[백준] 1697번: 숨바꼭질

https://www.acmicpc.net/problem/1697

initial

This is very simple compared to Programmers BFS like 경주로 건설. This is a 1d list where moves is +1,-1 or *2. I forgot to check the validity of next_move though where I should have added if next_move is within the 1d list.

my correct solution:

from collections import deque

n,m = map(int,input().split())
queue = deque()
queue.append((n,0))
visited = [False for _ in range(100000+1)]
visited[n]=True

while queue:
    cur_pos, cur_cost = queue.popleft()
    if cur_pos==m:
        print(cur_cost)
    moves = [cur_pos+1, cur_pos-1, cur_pos*2]
    for move in moves:
        if 0<=move<=100000:
            if not visited[move]:
                queue.append((move,cur_cost+1))
                visited[move]=True

complexity

1. Space Complexity:

   • The queue is a deque used for BFS, and it can contain at most O(n) elements in the worst case (where n is the maximum possible value of 100000).
   • The visited list is used to keep track of visited positions, and it has a fixed size of 100000 + 1, so it takes O(1) space.
   • Other variables (cur_pos and cur_cost) take constant space.

   The overall space complexity is O(n).

2. Time Complexity:

   • In the worst case, the BFS algorithm explores all possible positions between 0 and 100000.
   • For each position, it explores three potential moves: cur_pos + 1, cur_pos - 1, and cur_pos * 2.
   • Since each position is explored at most once, the time complexity is proportional to the number of positions explored.

   The worst-case time complexity is O(n).

The code efficiently finds the shortest path from n to m using BFS, and its time and space complexity are both linear in the range of possible positions (100000 in this case).