[BOJ] 13549 : 숨바꼭질 3 [그래프이론](Python)

문제 링크

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

13549번: 숨바꼭질 3

소스 코드

import heapq

def main():
    n,k = map(int,input().split())
    limit = 10**5 + 1 # 최댓값
    INF = 10**9 # 비용 초기화
    arr = [INF] * (limit+1) 
    arr[n] = 0

    hq = []
    heapq.heappush(hq, (0,n))

    while hq: # 다익스트라
        cost, x = heapq.heappop(hq)
        if x == k: # 목표에 도달하면
            print(cost)
            exit(0)

        # (우로 이동, 좌로 이동, 순간 이동)
        for nx,ncost in ((x+1,1), (x-1,1), (x*2,0)):
            # 범위 만족 & 기존보다 효율적
            if 0 <= nx < limit and cost + ncost < arr[nx]:
                arr[nx] = cost + ncost # 갱신
                heapq.heappush(hq, (arr[nx], nx))
    
    print(arr[k])
    
if __name__ == "__main__":
    main()

 

해설

• 다익스트라 (BFS도 가능)

아아 생각보다 아주 열 받는 문제였습니다.

조건을 세심하게 설정하지 않으면 계속 틀리더라구요..

처음엔 BFS로 시도를 하다가 nx의 입력 순서에 따라 정답이 달라지는 것을 알게 되어서 관뒀습니다.

그렇게 정답을 맞히는 것은 큰 의미가 없으니까요.

 

각종 변수 초기화

limit : 문제 조건을 보시면 100,000을 넘어가지 않습니다. 따라서 이를 벗어나지 않도록 값을 세팅합니다.

INF : 지금까지의 이동 비용을 계산하기 앞서 넘을 수 없는 큰 값으로 초기화 합니다.

arr : INF 값을 이용하여 100,001 개의 값을 가진 리스트를 만듭니다. 1을 더하는 이유는 다들 아시겠죠?

arr[n] = 0 : 시작점이니까 비용을 0으로 초기화 합니다.

hq : 힙입니다. 비용 0과, 시작점 n을 튜플로 집어 넣습니다.

n,k = map(int,input().split())
limit = 10**5 + 1 # 최댓값
INF = 10**9 # 비용 초기화
arr = [INF] * (limit+1) 
arr[n] = 0

hq = []
heapq.heappush(hq, (0,n))

 

최단 거리 구하기

종료 조건은 당연히도 현재의 노드가 목표 노드와 동일할 때 입니다.

따라서 이 조건을 만족할 때는 바로 값을 출력하고 프로그램을 종료합니다.

while hq: # 다익스트라
    cost, x = heapq.heappop(hq)
    if x == k: # 목표에 도달하면
        print(cost)
        exit(0)

 

다음으로 우측, 좌측, 순간 이동을 하나씩 탐색합니다.

이때 순간 이동은 비용이 0이므로 이를 구분할 수 있도록 (이동할 위치, 추가 비용)의 형태로 값을 받습니다.

그래서 변수명은 nx, ncost로 지정했습니다.

 

이동할 위치인 nx는 우리가 만든 리스트 범위를 벗어나면 안됩니다.

따라서 nx가 범위를 만족함과 동시에, (현재까지의 비용 + 추가비용)이 (지금까지 계산해놓은 값)보다 작아야 합니다.

지금 추가로 처리하는 작업이 더 비효율적이라면 굳이 값을 갱신할 필요가 없겠죠.

 

이 두 조건을 만족하는 경우 값을 갱신하고 '갱신된 비용'을 기준으로 heappush 합니다.

즉, 비용이 가장 작은 것부터 추가 탐색을 진행한다는 뜻입니다.

# (우로 이동, 좌로 이동, 순간 이동)
for nx,ncost in ((x+1,1), (x-1,1), (x*2,0)):
    # 범위 만족 & 기존보다 효율적
    if 0 <= nx < limit and cost + ncost < arr[nx]:
        arr[nx] = cost + ncost # 갱신
        heapq.heappush(hq, (arr[nx], nx))

 

마지막 프린트문은 사실 무시하셔도 됩니다.

도착점에 도달하지 못하는 경우는 존재하지 않기 때문이죠..!

처음엔 저 출력문만 적어놨다가 조금 비효율적인 것 같아서 종료 조건을 추가해서 흔적이 남아있는 것입니다 😅