(Python) - BOJ(1697번) : 숨바꼭질

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

1697번: 숨바꼭질

---

• 해설 : 

수빈이는 A라는 위치에 있고 동생은 B라는 위치에 있다 (A, B)는 모두 자연수

수빈이는 현재위치 X에서 X+1, X-1, 2*X의 이동을 할 수 있다고 한다.

모든 연산엔 시간이 1씩 소모된다고 했을 때 동생을 찾는데 소모되는 최소 비용을 찾는 문제이다.

 

 

 

 

---

• 풀이 :

현재위치 X에 X+1, X-1, X*2 연산을 진행하며 X를 만날 때까지 실행되게 하였다. 

지금 보니 매우 비효율적으로 해결한 것 같다. 시리즈 문제인 숨바꼭질 2, 3, 4 ····· 가 있는데 이것도 풀어봐야겠다.

 

 

 

---

• 소스코드 : 

 

def bfs(start):
    X = start
    if X == M:
        print(i)
        exit()
    if 0 < X <= 100000:
        if visited[X-1] == 0:
            queue[-1].append(X-1)
            visited[X-1] = 1
    if 0 <= X < 100000:
        if visited[X+1] == 0:
            queue[-1].append(X+1)
            visited[X+1] = 1
    if X*2 <= 100000:
        if visited[X*2] == 0:
            queue[-1].append(X*2)
            visited[X*2] = 1
 
if __name__ == "__main__":
    N,M = map(int,input().split())
    visited = [0 for _ in range(100001)]
    queue = []
    queue.append([N])
    i=0
 
    while queue[-1]:
        queue.append([])
        for z in queue[i]:
            bfs(z)
        i+=1