[백준] 12851 숨바꼭질 2

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

동생이 위치한 곳으로 도착하는 최단시간을 구해야하므로 다익스트라를 이용하였습니다.

2) 알고리즘

• 다익스트라

3) 풀이 코드

사용 언어 - Python

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

def solution(start):
    heap = [(0, start)]                     # 시작 시간, 시작 좌표
    cnt = 0                                 # 동생에게 최단시간에 도착하는 방법 개수 카운트

    while heap:
        node = heapq.heappop(heap)         
        if distance[node[1]] >= node[0]:    # 다음 위치로 이동하는게 최소시간인 경우
            distance[node[1]] = node[0]     # 최소 시간 갱신
            if node[1] == K:                # 동생이 있는곳이라면 이동 방법 개수 카운트
                cnt += 1

            if node[1] - 1 >= 0:                                # 한칸 뒤로 이동이 유효한 범위인 경우 추가
                heapq.heappush(heap, (node[0]+1, node[1]-1))
            if node[1] + 1 <= 100000:                           # 한칸 앞으로 이동이 유효한 범위인 경우 추가
                heapq.heappush(heap, (node[0]+1, node[1]+1))
            if node[1] * 2 <= 100000:                           # 두배 이동이 유효한 범위인 경우 추가
                heapq.heappush(heap, (node[0]+1, node[1]*2))

    return cnt                                      # 동생에게 이동하는 방법 개수 반환

N, K = map(int, sys.stdin.readline().split())       # 수빈이 위치, 동생 위치
distance = [1e10] * 100001                          # 이동 가능한 범위의 리스트, 해당 좌표로 이동하기 위한 최소시간

answer = solution(N)                                # 수빈이 위치에서 출발

print(distance[K])                                  # 출력
print(answer)

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

특별히 없습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

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

12851번: 숨바꼭질 2

 

 

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