S1 1697. 숨바꼭질

문제 보기 :  1697번: 숨바꼭질

---

문제

• 정답률 : 26%

---

작성 코드

from collections import deque

def find(start,bro):
    if start >= bro: #동생이 더 앞에 있는 경우
        return start-bro

    visited = [-1]*100001
    visited[start] = 0

    dd = deque([start])
    while dd:
        now = dd.popleft()
        can = (now-1,now+1,2*now)
        for jump in can:
            if jump == bro :
                return visited[now]+1
            if 0<=jump<=100000 and visited[jump]==-1:
                visited[jump] = visited[now]+1
                dd.append(jump)
    return visited[bro]

start, bro = map(int,input().split())
print(find(start,bro))

---

풀이

1차원 좌표로 풀이하는 방법인데, bfs 알고리즘을 사용했다.

동생이 수빈이 위치보다 앞에 있는 경우 무조건 -1로 n번 해서 이동해야하니, 바로 start-bro로 빼줬다.
그리고 visited를 -1로 둬서 해당 칸으로 오기 위해 거쳐야하는 이동 횟수를 두었다.
(딕셔너리로 대체라고 생각하면 편할 것 같다.
if 이동가능한 좌표 in 어떤 dictionary:
                 pass
else:
                 어떤 딕셔너리[이동가능한좌표] = 방금 움직인 횟수 + 1)