백준 13549번 숨바꼭질 3

정보

문제 바로가기 [클릭]

난이도: Gold5

관련 개념: #그래프이론 #그래프탐색 #너비 우선 탐색 #다익스트라 #자료구조 #0-1 너비 우선 탐색

---

조건

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

---

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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

출력

2

---

힌트

수빈이가 5-10-9-18-17 순으로 가면 2초만에 동생을 찾을 수 있다.

---

코드(파이썬)

from collections import deque


s, e = map(int, input().split())
graph = {i:[i-1, i+1] + ([i*2] if i*2 < 100001 else []) for i in range(1, 100000)}
graph[0] = [1]
graph[100000] = [99999]
visited = [0] * 100001
result = 0

if s > e:
    result = s - e
else:
    queue = deque([s])
    tmp = s*2
    while 0 < tmp <= 100000:
        visited[tmp] = 1
        queue.append(tmp)
        tmp *= 2
            
    while queue:
        if e in queue:
            break
        
        for _ in range(len(queue)):
            for tmp in graph[queue.popleft()]:
                if visited[tmp] == 0:
                    visited[tmp] = 1
                    queue.append(tmp)
                    tmp *= 2
                    
                    while 0 < tmp <= 100000:
                        if visited[tmp] == 0:
                            visited[tmp] = 1
                            queue.append(tmp)
                        tmp *= 2

        result += 1
    
print(result)

---

특이사항

• BFS를 이용해 해결하였으나 최적화를 거치지 않아 메모리, 속도 측면에서 불리
• 내 코드(56,220KB, 188ms)에 비해 우수한 코드(바로가기, 30,864KB, 72ms)와 비교

  • def F(N,K):
        if N>=K:return N-K
        elif K==1:return 1
        elif K%2:return min(F(N,K-1),F(N,K+1))+1
        else:return min(K-N,F(N,K//2))
    N,K=map(int,input().split())
    print(F(N,K))
    

  • BFS대신 DFS를 이용
  • 간단하고 효율적인 풀이방식

---

참고문헌

-