[백준] 13549 : 숨바꼭질3 / python

1. 문제 설명

13549번: 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다.

수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.

수빈이는 걷거나 순간이동을 할 수 있다.

만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.

순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때,

수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

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

출력

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

 

2. 풀이 전 계획과 생각

• 5 17 → 4
• 수빈이가 5-10-9-18-17 순으로 가면 2초만에 동생을 찾을 수 있다.
• 텔레포트하는 경우, 0초이므로, 가장 먼저 고려해야 한다.

 

3. 풀이하면서 막혔던 점과 고민

🤔 무조건 2배 해준다고 좋은 것이 아니다. 모든 경우의 수를 다 따져야 한다.

하지만 입력값이 너무 크다. 어떻게 하면 좋을까?

 

💡 Hint!

⇒ 그래프 탐색을 사용하여, 최단 경로를 찾아주면 된다.

 

🤔 Graph가 주어져있지 않다.

주어진 정보들을 가지고 정점과 간선을 정의할 수 없을까?

• 정점
  • 점의 번호가 곧 정점의 번호
• 간선
  • 이동을 의미하는 것을 간선으로 표현
  • 각 점마다 -1, +1, *2인 점을 향하는 방향성 간선

 

🤔  BFS 사용하여, 최단경로를 구하기에는, N*2의 가중치가 0이다.

가중치가 다르기에, 다익스트라로 그래프를 탐색하여, 최단거리를 구하자.

1. visited 라는 방문 체크 배열을 만들어두고, N부터 탐색을 진행한다.
2. 탐색은 3방향으로, N-1, N+1, N*2 이다.
3. visited의 인덱스 범위 배열을 넘어가지 않게 조건을 주고,
4. 만약 정점 K에 도달했다면 시간을 출력하고 종료한다.

 

4. 풀이

import sys, heapq
input = sys.stdin.readline

N, K = map(int,input().split())
visited = [False] * 100001
visited[N] = True
hq = [([0, N])]

while hq:
    time, pos = heapq.heappop(hq)
    if pos == K:
        print(time)
        break
       
    next_pos = pos*2
    if next_pos < len(visited) and not visited[next_pos]:
        visited[next_pos] = True
        heapq.heappush(hq,(time, next_pos))
    
    for next_pos in (pos+1, pos-1):
        if next_pos >= 0 and next_pos < len(visited) and not visited[next_pos]:
            visited[next_pos] = True
            heapq.heappush(hq,(time+1, next_pos))

 

5. 풀이 후 알게된 개념과 소감

• 여러 곳으로 이동할 수 있음으로, (= 여러 vertex로 이동할 수 있음으로 = 여러 edge들이 있음으로)
  하나의 그래프로 볼 수 있다.
• 최단경로를 구하는데, 가중치가 다르면, 다익스트라 알고리즘으로 해결할 수 있다.