[백준] 13549 숨바꼭질 3

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

 수빈이가 동생의 위치로 이동하는데 걸리는 최소의 시간을 구해야 하므로 다익스트라를 이용하였습니다.

2) 알고리즘

• 다익스트라

3) 풀이 코드

사용 언어 - Python

import sys
import heapq
sys.stdin = open('input.txt')

def solution(start):        
    heap = [(0, start)]             # 처음에 시작은 0초, 처음에 출발하는 수빈이 위치
    
    while heap:
        if road[K] != -1:           # 동생한테 도착했다면 종료
            return
        node = heapq.heappop(heap)
        if 0 <= node[1] <= 100000 and road[node[1]] == -1:              # 다음에 움직일 곳이 범위 내이고, 아직 방문하지 않았으면
            road[node[1]] = node[0]                                     # 다음 위치에 소요되는 시간 기록
            heapq.heappush(heap, (road[node[1]] + 1, node[1] - 1))      # 1초가 걸려 이동하는 좌우 추가
            heapq.heappush(heap, (road[node[1]] + 1, node[1] + 1))
            heapq.heappush(heap, (road[node[1]], node[1] * 2))          # 0초가 걸려 이동하는 텔레포트 위치 추가

N, K = map(int, sys.stdin.readline().split())       # 수빈이의 위치, 동생의 위치
road = [-1] * 100001                                # 수빈이와 동생이 이동 가능한 영역

solution(N)         # 수빈이 위치를 기준으로 다익스트라 탐색

print(road[K])      # 출력

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다