[ 백준 13549 ] ( python ) 숨바꼭질 3

 

📚 숨바꼭질 3

 

문제

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

# ✨ 입력
import sys
from collections import deque
input = sys.stdin.readline
N,K = map(int,input().split())
INF = 2147000000

# ✨ BFS
def BFS(N,K):
    dq = deque([])
    dq.append((0,N))
    ch_board = [INF] * (100001)
    ch_board[N] = 0
    while dq:
        val, node = dq.popleft()
        for x in [(1,node+1),(1,node-1),(0,node*2)]:
            if 0<=x[1]<100001:
                if ch_board[x[1]] > val+x[0]:
                    ch_board[x[1]] = val+x[0]
                    dq.append((ch_board[x[1]],x[1]))
    return ch_board[K]

# ✨ 출력
print(BFS(N,K))

입력

• BFS를 쓰기 위해 deque를 import해오고 입력받는다

BFS 함수

• N과 K를 인자로 받아 BFS
• ch_board에 가장 빠른 거리를 갱신해주며 입력해준다. 100001개를 INF로 초기화
• while문에서는
  • [(n+1,1),(n-1,1),(n*2,0)]을 돌면서
  • if문을 통해 list밖으로 벗어나지 않을 때만
  • 그 중에서도 ch_board에 저장된 값(시간)보다 val+x[0] 현재 node까지 온 시간과 다음 node(위치)까지 가는 시간이 적을 때
    
    • ch_board를 업데이트해두고
    • dq에 값을 추가해준다

 

 

정답코드 ( 다익스트라 | Dijkstra )

# ✨ 입력
import sys
import heapq
input = sys.stdin.readline
N,K = map(int,input().split())
INF = 2147000000

# ✨ dijkstra 함수
def dijkstra(N,K):
    dist = [INF]*(100001)
    dist[N] =0 
    hq = []
    heapq.heappush(hq,(0,N))
    while hq:
        w,n = heapq.heappop(hq)
        for nx in [(n+1,1),(n-1,1),(n*2,0)]:
            if 0<=nx[0]<100001 and dist[nx[0]] > w + nx[1]:
                dist[nx[0]] = w + nx[1]
                heapq.heappush(hq,(dist[nx[0]],nx[0]))
    print(dist[K])
dijkstra(N,K)

입력

• dijkstra를 쓰기 위해 heapq를 import해오고 입력받는다

dijkstra 함수

• dist라는 list를 INF 100001개로 초기화해준 후
• dist[N] = 누나 위치를 0으로 초기화한다
• hq에 (time, N) == (0,N)을 넣어준다
• while문을 돌면서
  • for문을 통해 BFS랑 같은 방식으로 돌아준다

 

heap이냐 deque냐의 문제이지 방법은 같다

 

 

 

⭐ 배움

• 최단거리!