[백준] 13549 숨바꼭질3 python

숨바꼭질 3 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

95995

24571

16415

24.222%

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1 복사

5 17

예제 출력 1 복사

2

---

문제 풀이

전형적인 BFS만 풀다보니까 BFS의 개념을 놓치고 있어서 못 풀었다.

BFS는 너비 우선 탐색이니까,

우선은 가능한 인접 노드 (즉, in_range인 경우 그리고 방문하지 않는 경우)는 다 queue에 저장하는 것이다.

 

여기서 추가적으로 순간이동하는 움직임에 대한 우선순위를 주기 위해

appendLeft()를 넣는다

 

from collections import deque

n, m = map(int, input().split())

# 수빈이가 있는 위치, 동생이 있는 위치

result = 0

visited = [-1 for _ in range(100001)]

print(visited)

queue = deque()

queue.append(n)

visited[n] = 0

while queue:

    x = queue.popleft()

    if x == m:

        print(visited[x])

        break

    # 방문을 어떤 걸 해야하는거지?

    # 너비 탐색을 하려면 인접노드로 가야하는데

    if 0 <= x-1 <= 100000 and visited[x-1] == -1:

        visited[x-1] = visited[x] + 1

        queue.append(x-1)

    if 0 <= x*2 <= 100000 and visited[2*x] == -1:

        queue.appendleft(x*2)

        visited[2*x] = visited[x]

    if 0 <= x+1 <= 100000 and visited[x+1] == -1:

        visited[x+1] = visited[x] + 1

        queue.append(x+1)

# while True:

#     if (n == m):

#         break

#     else:

#         if (n*2 <= m):

#             n = n*2

#             continue

#         if (n < m):

#             n += 1

#         else:

#             n -= 1

#         result += 1

               

# print(result)