백준 12851번 숨바꼭질 2

정보

문제 바로가기 [클릭]

난이도: Gold5

관련 개념: #그래프이론 #그래프탐색 #너비 우선 탐색

---

조건

시간 제한	메모리 제한
2 초	512 MB

---

문제

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

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

---

입력

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

---

출력

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

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

---

예제 입출력 1

입력

5 17

출력

4
2

---

코드(파이썬)

from collections import deque


n, k = map(int, input().split())
queue = deque([n])
v = [1] * (100001)
cnt = 0

while queue and k not in queue:
    tmp_v = set()
    for _ in range(len(queue)):
        now = queue.popleft()
        if v[now]:
            tmp_v.add(now)
            
            if now > 0 and v[now-1]:
                queue.append(now-1)

            if now < 100000 and v[now+1]:
                queue.append(now+1)
            
            if now*2 <= 100000 and v[now*2]:
                queue.append(now*2)
    
    for i in tmp_v:
        v[i] = 0
    cnt += 1

print(cnt)
print(queue.count(k))

---

특이사항

• 해결방법
  • BFS를 이용해 트리의 층마다 탐색
  • 다음 탐색 예정 큐에 k 값이 있다면 종료

---

참고문헌

-